View source for Arithmetic function

{{list|date=July 2020}}
{{short description|Function whose domain is the positive integers}}
In [[Number theory|number theory]], an '''arithmetic''', '''arithmetical''', or '''number-theoretic function'''<ref>{{harvtxt|Long|1972|p=151}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=58}}</ref> is generally any [[Function (mathematics)|function]] ''f''(''n'') whose domain is the [[Natural number|positive integers]] and whose range is a [[Subset|subset]] of the [[Complex number|complex number]]s.<ref>Niven & Zuckerman, 4.2.</ref><ref>Nagell, I.9.</ref><ref>Bateman & Diamond, 2.1.</ref> Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of ''n''".<ref>Hardy & Wright, intro. to Ch. XVI</ref> There is a larger class of number-theoretic functions that do not fit this definition, for example, the [[Prime-counting function|prime-counting function]]s. This article provides links to functions of both classes.

An example of an arithmetic function is the [[Divisor function|divisor function]] whose value at a positive integer ''n'' is equal to the number of divisors of ''n''.

Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of [[Ramanujan's sum]].

==Multiplicative and additive functions==
An arithmetic function ''a'' is
* '''completely additive''' if ''a''(''mn'') = ''a''(''m'') + ''a''(''n'') for all natural numbers ''m'' and ''n'';
* '''completely multiplicative''' if ''a''(''mn'') = ''a''(''m'')''a''(''n'') for all natural numbers ''m'' and ''n'';

Two whole numbers ''m'' and ''n'' are called coprime if their greatest common divisor is 1, that is, if there is no [[Prime number|prime number]] that divides both of them.

Then an arithmetic function ''a'' is
* '''[[Additive function|additive]]''' if ''a''(''mn'') = ''a''(''m'') + ''a''(''n'') for all coprime natural numbers ''m'' and ''n'';
* '''multiplicative''' if ''a''(''mn'') = ''a''(''m'')''a''(''n'') for all coprime natural numbers ''m'' and ''n''.

==Notation==
In this article, <math display="inline">\sum_p f(p)</math> and <math display="inline">\prod_p f(p)</math> mean that the sum or product is over all [[Prime number|prime number]]s:
<math display="block">\sum_p f(p) = f(2) + f(3) + f(5) + \cdots</math>
and
<math display="block">\prod_p f(p)= f(2)f(3)f(5)\cdots.</math>
Similarly, <math display="inline">\sum_{p^k} f(p^k)</math> and <math display="inline">\prod_{p^k} f(p^k)</math> mean that the sum or product is over all [[Prime power|prime power]]s with strictly positive exponent (so {{math|1=''k'' = 0}} is not included):
<math display="block">\sum_{p^k} f(p^k) = \sum_p\sum_{k > 0} f(p^k) = f(2) + f(3) + f(4) +f(5) +f(7)+f(8)+f(9)+\cdots.</math>

The notations <math display="inline">\sum_{d\mid n} f(d)</math> and <math display="inline">\prod_{d\mid n} f(d)</math> mean that the sum or product is over all positive divisors of ''n'', including 1 and ''n''. For example, if {{math|1=''n'' = 12}}, then
<math display="block">\prod_{d\mid 12} f(d) = f(1)f(2) f(3)  f(4)  f(6)  f(12). </math>

The notations can be combined: <math display="inline">\sum_{p\mid n} f(p)</math> and <math display="inline">\prod_{p\mid n} f(p)</math> mean that the sum or product is over all prime divisors of ''n''. For example, if ''n'' = 18, then
<math display="block">\sum_{p\mid 18} f(p) = f(2) + f(3), </math>
and similarly <math display="inline">\sum_{p^k\mid n} f(p^k)</math> and <math display="inline">\prod_{p^k\mid n} f(p^k)</math> mean that the sum or product is over all prime powers dividing ''n''. For example, if ''n'' = 24, then
<math display="block">\prod_{p^k\mid 24} f(p^k) = f(2) f(3) f(4) f(8). </math>

==Ω(''n''), ''ω''(''n''), ''ν''<sub>''p''</sub>(''n'') – prime power decomposition==
The [[Fundamental theorem of arithmetic|fundamental theorem of arithmetic]] states that any positive integer ''n'' can be represented uniquely as a product of powers of primes: <math> n = p_1^{a_1}\cdots p_k^{a_k} </math> where  ''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>''k''</sub> are primes and the ''a<sub>j</sub>'' are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define the [[P-adic valuation|''p''-adic valuation]] '''ν<sub>''p''</sub>(''n'')''' to be the exponent of the highest power of the prime ''p'' that divides ''n''. That is, if ''p'' is one of the ''p''<sub>''i''</sub> then ''ν''<sub>''p''</sub>(''n'') = ''a''<sub>''i''</sub>, otherwise it is zero.  Then
<math display="block">n = \prod_p p^{\nu_p(n)}.</math>

In terms of the above the [[Prime omega function|prime omega function]]s ω and Ω are defined by
{{block indent | em = 1.5 | text = ''ω''(''n'') = ''k'',}}
{{block indent | em = 1.5 | text = Ω(''n'') = ''a''<sub>1</sub> + ''a''<sub>2</sub> + ... + ''a''<sub>''k''</sub>.}}

To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of ''n'' and the corresponding ''p''<sub>''i''</sub>, ''a''<sub>''i''</sub>, ω, and Ω.

==Multiplicative functions==
===σ<sub>''k''</sub>(''n''), τ(''n''), ''d''(''n'') – divisor sums===
'''[[Divisor function|σ<sub>''k''</sub>(''n'')]]''' is the sum of the ''k''th powers of the positive divisors of ''n'', including 1 and ''n'', where ''k'' is a complex number.

'''σ<sub>1</sub>(''n'')''', the sum of the (positive) divisors of ''n'', is usually denoted by '''σ(''n'')'''.

Since a positive number to the zero power is one, '''σ<sub>0</sub>(''n'')''' is therefore the number of (positive) divisors of ''n''; it is usually denoted by '''''d''(''n'')''' or '''τ(''n'')''' (for the German ''Teiler'' = divisors).

<math display="block">\sigma_k(n) = \prod_{i=1}^{\omega(n)} \frac{p_i^{(a_i+1)k}-1}{p_i^k-1}= \prod_{i=1}^{\omega(n)} \left(1 + p_i^k + p_i^{2k} + \cdots + p_i^{a_i k}\right).</math>

Setting ''k'' = 0 in the second product gives
<math display="block">\tau(n) = d(n) = (1 + a_{1})(1+a_{2})\cdots(1+a_{\omega(n)}).</math>

===φ(''n'') – Euler totient function===
'''φ(''n'')''', the Euler totient function, is the number of positive integers not greater than ''n'' that are coprime to ''n''.

<math display="block">\varphi(n) = n \prod_{p\mid n} \left(1-\frac{1}{p}\right)
= n \left(\frac{p_1 - 1}{p_1}\right)\left(\frac{p_2 - 1}{p_2}\right) \cdots \left(\frac{p_{\omega(n)} - 1}{p_{\omega(n)}}\right)
.</math>

===J<sub>''k''</sub>(''n'') – Jordan totient function===
'''J<sub>''k''</sub>(''n'')''', the Jordan totient function, is the number of ''k''-tuples of positive integers all less than or equal to ''n'' that form a coprime (''k'' + 1)-tuple together with ''n''. It is a generalization of Euler's  totient, {{math|1=φ(''n'') = J<sub>1</sub>(''n'')}}.
<math display="block">J_k(n) = n^k \prod_{p\mid n} \left(1-\frac{1}{p^k}\right)
= n^k \left(\frac{p^k_1 - 1}{p^k_1}\right)\left(\frac{p^k_2 - 1}{p^k_2}\right) \cdots \left(\frac{p^k_{\omega(n)} - 1}{p^k_{\omega(n)}}\right)
.</math>

===μ(''n'') – Möbius function===
'''μ(''n'')''', the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below.

<math display="block">\mu(n)=\begin{cases}
(-1)^{\omega(n)}=(-1)^{\Omega(n)} &\text{if }\; \omega(n) = \Omega(n)\\
0&\text{if }\;\omega(n) \ne \Omega(n).
\end{cases}</math>

This implies that μ(1) = 1. (Because Ω(1) =  ω(1) = 0.)

===τ(''n'') – Ramanujan tau function===
'''[[Ramanujan tau function|τ(''n'')]]''', the Ramanujan tau function, is defined by its [[Generating function|generating function]] identity:

<math display="block">\sum_{n\geq 1}\tau(n)q^n=q\prod_{n\geq 1}(1-q^n)^{24}.</math>

Although it is hard to say exactly what  "arithmetical property of ''n''" it "expresses",<ref>Hardy, ''Ramanujan'', § 10.2</ref> (''τ''(''n'') is (2π)<sup>−12</sup> times the ''n''th Fourier coefficient in the q-expansion of the modular discriminant function)<ref>Apostol, ''Modular Functions ...'', § 1.15, Ch. 4, and ch. 6</ref> it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σ<sub>''k''</sub>(''n'') and ''r''<sub>''k''</sub>(''n'') functions (because these are also coefficients in the expansion of [[Modular form|modular form]]s).

===''c''<sub>''q''</sub>(''n'') – Ramanujan's sum===
'''[[Ramanujan's sum|''c''<sub>''q''</sub>(''n'')]]''', Ramanujan's sum, is the sum of the ''n''th powers of the primitive ''q''th roots of unity:
<math display="block">c_q(n) = \sum_{\stackrel{1\le a\le q}{ \gcd(a,q)=1}} e^{2 \pi i \tfrac{a}{q} n}.</math>

Even though it is defined as a sum of complex numbers (irrational for most values of ''q''), it is an integer. For a fixed value of ''n'' it is multiplicative in ''q'':
:'''If ''q'' and ''r'' are coprime''', then <math>c_q(n)c_r(n)=c_{qr}(n).</math>

===''ψ''(''n'') - Dedekind psi function===
The Dedekind psi function, used in the theory of modular functions, is defined by the formula
<math display="block"> \psi(n) = n \prod_{p|n}\left(1+\frac{1}{p}\right).</math>

==Completely multiplicative functions==
===λ(''n'') – Liouville function===
'''''λ''(''n'')''', the Liouville function, is  defined by
<math display="block">\lambda (n) = (-1)^{\Omega(n)}.</math>

===''χ''(''n'') – characters===
All '''[[Dirichlet character]]s ''χ''(''n'')''' are completely multiplicative.  Two characters have special notations:

The '''principal character (mod ''n'')''' is denoted by ''χ''<sub>0</sub>(''a'') (or ''χ''<sub>1</sub>(''a'')). It is defined as
<math display="block"> \chi_0(a) = \begin{cases}
1 & \text{if } \gcd(a,n) = 1, \\
0 & \text{if } \gcd(a,n) \ne 1.
\end{cases} </math>

The '''quadratic character (mod ''n'')''' is denoted by the [[Jacobi symbol]] for odd ''n'' (it is not defined for even ''n''):
<math display="block">\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{a_1}\left(\frac{a}{p_2}\right)^{a_2}\cdots \left(\frac{a}{p_{\omega(n)}}\right)^{a_{\omega(n)}}.</math>

In this formula <math>(\tfrac{a}{p})</math> is the [[Legendre symbol]], defined for all integers ''a'' and all odd primes ''p'' by
<math display="block">
\left(\frac{a}{p}\right) = \begin{cases}
\;\;\,0 & \text{if } a \equiv 0 \pmod p,
\\+1 & \text{if }a \not\equiv 0\pmod p \text{ and for some integer }x, \;a\equiv x^2\pmod p
\\-1 & \text{if there is no such } x. \end{cases}</math>

Following the normal convention for the empty product, <math>\left(\frac{a}{1}\right) = 1.</math>

==Additive functions==
===''ω''(''n'') – distinct prime divisors===
'''ω(''n'')''', defined above as the number of distinct primes dividing ''n'', is additive (see [[Prime omega function]]).

==Completely additive functions==
===Ω(''n'') – prime divisors===
'''Ω(''n'')''', defined above as the number of prime factors of ''n'' counted with multiplicities, is completely additive (see [[Prime omega function]]).

===''ν''<sub>''p''</sub>(''n'') – [[P-adic valuation|''p''-adic valuation]] of an integer ''n''===
For a fixed prime ''p'', '''''ν''<sub>''p''</sub>(''n'')''', defined above as the exponent of the largest power of ''p'' dividing ''n'', is completely additive.

===Logarithmic derivative=== 
<math>\operatorname{ld}(n)=\frac{D(n)}{n} = \sum_{\stackrel{p\mid n}{p\text{ prime}}} \frac {v_p(n)} {p}</math>, where <math>D(n)</math> is the arithmetic derivative.

==Neither multiplicative nor additive==

==={{pi}}(''x''), Π(''x''), ''θ''(''x''), ''ψ''(''x'') – prime-counting functions===
These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the [[Prime number theorem|prime number theorem]]. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

'''[[Prime-counting function|{{pi}}(''x'')]]''', the prime-counting function, is the number of primes not exceeding ''x''. It is the summation function of the [[Indicator function|characteristic function]] of the prime numbers.
<math display="block">\pi(x) = \sum_{p \le x} 1</math>

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ... It is the summation function of the arithmetic function which takes the value 1/''k'' on integers which are the k-th power of some prime number, and the value 0 on other integers.

<math display="block">\Pi(x) = \sum_{p^k\le x}\frac{1}{k}.</math>

'''[[Chebyshev function|''θ''(''x'')]]''' and '''''ψ''(''x'')''', the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding ''x''.
<math display="block">\vartheta(x)=\sum_{p\le x} \log p,</math>
<math display="block"> \psi(x) = \sum_{p^k\le x} \log p.</math>

The Chebyshev function ''ψ''(''x'') is the summation function of the von Mangoldt function just below.

===Λ(''n'') – von Mangoldt function===
'''[[Von Mangoldt function|Λ(''n'')]]''', the von Mangoldt function, is 0 unless the argument ''n'' is a prime power {{math|''p''<sup>''k''</sup>}}, in which case it is the natural log of the prime ''p'':
<math display="block">\Lambda(n) = \begin{cases}
\log p &\text{if } n = 2,3,4,5,7,8,9,11,13,16,\ldots=p^k \text{ is a prime power}\\
0&\text{if } n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;\text{ is not a prime power}.
\end{cases}</math>

===''p''(''n'') – partition function===
'''[[Partition function (number theory)|''p''(''n'')]]''', the partition function, is the number of ways of representing ''n'' as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:
<math display="block">p(n) = \left|\left\{ (a_1, a_2,\dots a_k): 0 < a_1 \le a_2 \le \cdots \le a_k\; \land \;n=a_1+a_2+\cdots +a_k \right\}\right|.</math>

===λ(''n'') – Carmichael function===
'''[[Carmichael function|''λ''(''n'')]]''', the Carmichael function, is the smallest positive number such that <math>a^{\lambda(n)}\equiv 1 \pmod{n}</math> &nbsp; for all ''a'' coprime to ''n''. Equivalently, it is the [[Least common multiple|least common multiple]] of the orders of the elements of the [[Multiplicative group of integers modulo n|multiplicative group of integers modulo ''n'']].

For powers of odd primes and for 2 and 4, ''λ''(''n'') is equal to the Euler totient function of ''n''; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of ''n'':
<math display="block">\lambda(n) = \begin{cases}
\;\;\phi(n) &\text{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\
\tfrac 1 2 \phi(n)&\text{if }n=8,16,32,64,\dots
\end{cases}</math>
and for general ''n'' it is the least common multiple of λ of each of the prime power factors of ''n'':
<math display="block">\lambda(p_1^{a_1}p_2^{a_2} \dots p_{\omega(n)}^{a_{\omega(n)}}) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_{\omega(n)}^{a_{\omega(n)}}) ].</math>

===''h''(''n'') – Class number===
'''[[Ideal class group|''h''(''n'')]]''', the class number function, is the order of the [[Ideal class group|ideal class group]] of an algebraic extension of the rationals with [[Discriminant|discriminant]] ''n''. The notation is ambiguous, as there are in general many extensions with the same discriminant. See [[Quadratic field|quadratic field]] and [[Cyclotomic field|cyclotomic field]] for classical examples.

===''r''<sub>''k''</sub>(''n'') – Sum of ''k'' squares===
'''[[Sum of squares function|''r''<sub>''k''</sub>(''n'')]]''' is the number of ways ''n'' can be represented as the sum of ''k'' squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

<math display="block">r_k(n) = \left|\left\{(a_1, a_2,\dots,a_k):n=a_1^2+a_2^2+\cdots+a_k^2\right\}\right|</math>

===''D''(''n'') – Arithmetic derivative===
Using the [[Differential operator#Notations|Heaviside notation]] for the derivative, the [[Arithmetic derivative|arithmetic derivative]] ''D''(''n'') is a function such that 
* <math> D(n) = 1</math> if ''n'' prime, and
* <math>D(mn) = m D(n) + D(m) n</math> (the [[Product rule|product rule]])

==Summation functions==
Given an arithmetic function ''a''(''n''), its '''summation function''' ''A''(''x'') is defined by
<math display="block"> A(x) := \sum_{n \le x} a(n) .</math>
''A'' can be regarded as a function of a real variable. Given a positive integer ''m'', ''A'' is constant along open intervals ''m'' < ''x'' < ''m'' + 1, and has a [[Classification of discontinuities|jump discontinuity]] at each integer for which ''a''(''m'') ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:
<math display="block"> A_0(m) := \frac 1 2 \left(\sum_{n < m} a(n) +\sum_{n \le m} a(n)\right) = A(m) - \frac 1 2 a(m) .</math>

Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find [[Asymptotic analysis|asymptotic behaviour]] for the summation function for large ''x''.

A classical example of this phenomenon<ref>Hardy & Wright, §§ 18.1–18.2</ref> is given by the [[Divisor summatory function|divisor summatory function]], the summation function of ''d''(''n''), the number of divisors of ''n'':
<math display="block">\liminf_{n\to\infty} d(n) = 2</math>
<math display="block">\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2</math>
<math display="block">\lim_{n\to\infty}\frac{d(1) + d(2)+ \cdots +d(n)}{\log(1) + \log(2)+ \cdots +\log(n)} = 1.</math>

An '''[[Average order of an arithmetic function|average order of an arithmetic function]]''' is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average".  We say that  ''g'' is an ''average order'' of ''f''   if
<math display="block"> \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) </math>

as ''x'' tends to infinity.  The example above shows that ''d''(''n'') has the average order log(''n'').<ref>{{cite book | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher={{wipe|Cambridge University Press}} | pages=36–55 | year=1995 | isbn=0-521-41261-7 }}</ref>

==Dirichlet convolution==
Given an arithmetic function ''a''(''n''), let ''F''<sub>''a''</sub>(''s''), for complex ''s'', be the function defined by the corresponding [[Dirichlet series]] (where it [[Convergent series|converges]]):<ref>Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.</ref>
<math display="block"> F_a(s) := \sum_{n=1}^\infty \frac{a(n)}{n^s} .</math>
''F''<sub>''a''</sub>(''s'') is called a [[Generating function|generating function]] of ''a''(''n''). The simplest such series, corresponding to the constant function ''a''(''n'') = 1 for all ''n'', is ''ζ''(''s'') the [[Riemann zeta function]].

The generating function of the Möbius function is the inverse of the zeta function:
<math display="block">\zeta(s)\,\sum_{n=1}^\infty\frac{\mu(n)}{n^s}=1, \;\;\Re s >1.</math>

Consider two arithmetic functions ''a'' and ''b'' and their respective generating functions ''F''<sub>''a''</sub>(''s'') and ''F''<sub>''b''</sub>(''s''). The product ''F''<sub>''a''</sub>(''s'')''F''<sub>''b''</sub>(''s'') can be computed as follows:
<math display="block"> F_a(s)F_b(s) = \left( \sum_{m=1}^{\infty}\frac{a(m)}{m^s} \right)\left( \sum_{n=1}^{\infty}\frac{b(n)}{n^s} \right) . </math>

It is a straightforward exercise to show that if ''c''(''n'') is defined by
<math display="block"> c(n) := \sum_{ij = n} a(i)b(j) = \sum_{i\mid n}a(i)b\left(\frac{n}{i}\right) , </math>
then <math display="block">F_c(s) = F_a(s) F_b(s).</math>

This function ''c'' is called the [[Dirichlet convolution]] of ''a'' and ''b'', and is denoted by <math>a*b</math>.

A particularly important case is convolution with the constant function ''a''(''n'') = 1 for all ''n'', corresponding to multiplying the generating function by the zeta function:
<math display="block">g(n) = \sum_{d \mid n}f(d).</math>

Multiplying by the inverse of the zeta function gives the Möbius inversion formula:
<math display="block">f(n) = \sum_{d\mid n}\mu\left(\frac{n}{d}\right)g(d).</math>

If ''f'' is multiplicative, then so is ''g''. If ''f'' is completely multiplicative, then ''g'' is multiplicative, but may or may not be completely multiplicative.

==Relations among the functions==
There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page [[Divisor sum identities|divisor sum identities]] contains many more generalized and related examples of identities involving arithmetic functions.

Here are a few examples:

===Dirichlet convolutions===
:<math>
\sum_{\delta\mid n}\mu(\delta)=
\sum_{\delta\mid n}\lambda\left(\frac{n}{\delta}\right)|\mu(\delta)|=
\begin{cases}
1 & \text{if } n=1\\
0 & \text{if } n\ne1
\end{cases}
</math> &nbsp; &nbsp; where ''λ'' is the Liouville function.<ref>Hardy & Wright, Thm. 263</ref>

:<math>\sum_{\delta\mid n}\varphi(\delta) = n.</math> &nbsp; &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 63</ref>
::<math>\varphi(n)
=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta
=n\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta}.
</math> &nbsp; &nbsp; &nbsp;  Möbius inversion
:<math>\sum_{d \mid n } J_k(d) = n^k.</math> &nbsp; &nbsp; &nbsp;<ref>see references at [[Jordan's totient function]]</ref>
::<math>
J_k(n)
=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta^k
=n^k\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta^k}.
</math> &nbsp; &nbsp; &nbsp;  Möbius inversion
:<math>\sum_{\delta\mid n}\delta^sJ_r(\delta)J_s\left(\frac{n}{\delta}\right) = J_{r+s}(n)</math> &nbsp; &nbsp; &nbsp;<ref>Holden et al. in external links The formula is Gegenbauer's</ref>
:<math>\sum_{\delta\mid n}\varphi(\delta)d\left(\frac{n}{\delta}\right) = \sigma(n).</math> &nbsp; &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 288–290</ref><ref>Dineva in external links, prop. 4</ref>
:<math>\sum_{\delta\mid n}|\mu(\delta)| = 2^{\omega(n)}.</math> &nbsp; &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 264</ref>
::<math>|\mu(n)|=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)2^{\omega(\delta)}.</math> &nbsp; &nbsp; &nbsp;  Möbius inversion
:<math>\sum_{\delta\mid n}2^{\omega(\delta)}=d(n^2).</math> &nbsp; &nbsp; &nbsp;
::<math>2^{\omega(n)}=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)d(\delta^2).</math> &nbsp; &nbsp; &nbsp;  Möbius inversion
:<math>\sum_{\delta\mid n}d(\delta^2)=d^2(n).</math> &nbsp; &nbsp; &nbsp;
::<math>d(n^2)=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)d^2(\delta).</math> &nbsp; &nbsp; &nbsp;  Möbius inversion
:<math>\sum_{\delta\mid n}d\left(\frac{n}{\delta}\right)2^{\omega(\delta)}=d^2(n).</math> &nbsp; &nbsp; &nbsp;
:<math>\sum_{\delta\mid n}\lambda(\delta)=\begin{cases}
&1\text{ if } n \text{ is a square }\\
&0\text{ if } n \text{ is not  square.}
\end{cases}</math>  &nbsp; &nbsp;  where λ is the Liouville function.
:<math>\sum_{\delta\mid n}\Lambda(\delta) = \log n.</math> &nbsp; &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 296</ref>
::<math>\Lambda(n)=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\log(\delta).</math> &nbsp; &nbsp; &nbsp;  Möbius inversion

===Sums of squares===
For all <math>k \ge 4,\;\;\; r_k(n) > 0.</math> &nbsp; &nbsp; ([[Lagrange's four-square theorem]]).

:<math>
r_2(n) = 4\sum_{d\mid n}\left(\frac{-4}{d}\right),
</math> <ref>Hardy & Wright, Thm. 278</ref>
where the [[Kronecker symbol]] has the values
:<math>
\left(\frac{-4}{n}\right) = 
\begin{cases}
+1&\text{if }n\equiv 1 \pmod 4 \\
-1&\text{if }n\equiv 3 \pmod 4\\
\;\;\;0&\text{if }n\text{ is even}.\\
\end{cases}
</math>

There is a formula for r<sub>3</sub> in the section on class numbers below.
<math display="block">
r_4(n) =
8 \sum_{\stackrel{d\mid n}{ 4\, \nmid \,d}}d =
8 (2+(-1)^n)\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d =
\begin{cases}
8\sigma(n)&\text{if } n \text{ is odd }\\
24\sigma\left(\frac{n}{2^\nu}\right)&\text{if } n \text{ is even }
\end{cases},
</math>
where {{math|1=''ν'' = ''ν''<sub>2</sub>(''n'')}}. &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 386</ref><ref>Hardy, ''Ramanujan'', eqs 9.1.2, 9.1.3</ref><ref>Koblitz, Ex. III.5.2</ref>

<math display="block">r_6(n) = 16 \sum_{d\mid n} \chi\left(\frac{n}{d}\right)d^2 - 4\sum_{d\mid n} \chi(d)d^2,</math>
where <math> \chi(n) = \left(\frac{-4}{n}\right).</math><ref name="Hardy & Wright, § 20.13">Hardy & Wright, § 20.13</ref>

Define the function {{math|1=''σ''<sub>''k''</sub><sup>*</sup>(''n'')}} as<ref>Hardy, ''Ramanujan'', § 9.7</ref>
<math display="block">\sigma_k^*(n) = (-1)^{n}\sum_{d\mid n}(-1)^d d^k=
\begin{cases}
\sum_{d\mid n} d^k=\sigma_k(n)&\text{if } n \text{ is odd }\\
\sum_{\stackrel{d\mid n}{ 2\, \mid \,d}}d^k -\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d^k&\text{if } n \text{ is even}.
\end{cases}
</math>

That is, if ''n'' is odd, {{math|1=''σ''<sub>''k''</sub><sup>*</sup>(''n'')}} is  the sum of the ''k''th powers of the divisors of ''n'', that is, {{math|1=''σ''<sub>''k''</sub>(''n''),}} and if ''n'' is even it is the sum of the ''k''th  powers of the even divisors of ''n'' minus the sum of the ''k''th  powers of the odd divisors of ''n''.

:<math>r_8(n) = 16\sigma_3^*(n).</math> &nbsp; &nbsp;<ref name="Hardy & Wright, § 20.13" /><ref>Hardy, ''Ramanujan'', § 9.13</ref>

Adopt the convention that Ramanujan's {{math|1=''τ''(''x'') = 0}} if ''x'' is '''not an integer.'''

:<math>
r_{24}(n) = \frac{16}{691}\sigma_{11}^*(n) + \frac{128}{691}\left\{
(-1)^{n-1}259\tau(n)-512\tau\left(\frac{n}{2}\right)\right\}
</math> &nbsp; &nbsp;<ref>Hardy, ''Ramanujan'', § 9.17</ref>

===Divisor sum convolutions===
Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the [[Power series#Multiplication and division|product of two power series]]:

:<math>  \left(\sum_{n=0}^\infty a_n x^n\right)\left(\sum_{n=0}^\infty b_n x^n\right)
= \sum_{i=0}^\infty \sum_{j=0}^\infty  a_i b_j x^{i+j}
= \sum_{n=0}^\infty \left(\sum_{i=0}^n a_i b_{n-i}\right) x^n
= \sum_{n=0}^\infty c_n x^n
.</math>

The sequence <math>c_n = \sum_{i=0}^n a_i b_{n-i}</math> is called the [[Convolution|convolution]] or the [[Cauchy product]] of the sequences ''a''<sub>''n''</sub> and ''b''<sub>''n''</sub>.
<br>These formulas may be proved analytically (see [[Eisenstein series]]) or by elementary methods.<ref>Williams, ch. 13; Huard, et al. (external links).</ref>

:<math>
\sigma_3(n) = \frac{1}{5}\left\{6n\sigma_1(n)-\sigma_1(n) + 12\sum_{0<k<n}\sigma_1(k)\sigma_1(n-k)\right\}.
</math> &nbsp; &nbsp;<ref name="Ramanujan, p. 146">Ramanujan, ''On Certain Arithmetical Functions'', Table IV; ''Papers'', p. 146</ref>

:<math>
\sigma_5(n) = \frac{1}{21}\left\{10(3n-1)\sigma_3(n)+\sigma_1(n) + 240\sum_{0<k<n}\sigma_1(k)\sigma_3(n-k)\right\}.
</math> &nbsp; &nbsp;<ref name="Koblitz, ex. III.2.8">Koblitz, ex. III.2.8</ref>

:<math>
\begin{align}
\sigma_7(n)
&=\frac{1}{20}\left\{21(2n-1)\sigma_5(n)-\sigma_1(n) + 504\sum_{0<k<n}\sigma_1(k)\sigma_5(n-k)\right\}\\
&=\sigma_3(n) + 120\sum_{0<k<n}\sigma_3(k)\sigma_3(n-k).
\end{align}
</math> &nbsp; &nbsp;<ref name="Koblitz, ex. III.2.8" /><ref>Koblitz, ex. III.2.3</ref>

:<math>
\begin{align}
\sigma_9(n)
&= \frac{1}{11}\left\{10(3n-2)\sigma_7(n)+\sigma_1(n) + 480\sum_{0<k<n}\sigma_1(k)\sigma_7(n-k)\right\}\\
&= \frac{1}{11}\left\{21\sigma_5(n)-10\sigma_3(n) + 5040\sum_{0<k<n}\sigma_3(k)\sigma_5(n-k)\right\}.
\end{align}
</math> &nbsp; &nbsp;<ref name="Ramanujan, p. 146" /><ref>Koblitz, ex. III.2.2</ref>

:<math>
\tau(n) = \frac{65}{756}\sigma_{11}(n) + \frac{691}{756}\sigma_{5}(n) - \frac{691}{3}\sum_{0<k<n}\sigma_5(k)\sigma_5(n-k),
</math> &nbsp; &nbsp; where ''τ''(''n'') is Ramanujan's function. &nbsp; &nbsp;<ref>Koblitz, ex. III.2.4</ref><ref>Apostol, ''Modular Functions ...'', Ex. 6.10</ref>

Since ''σ''<sub>''k''</sub>(''n'') (for natural number ''k'') and ''τ''(''n'') are integers, the above formulas can be used to prove congruences<ref>Apostol, ''Modular Functions...'', Ch. 6 Ex. 10</ref> for the functions. See [[Ramanujan tau function]] for some examples.

Extend the domain of the partition function by setting {{math|1=''p''(0) = 1.}}

:<math>
p(n)=\frac{1}{n}\sum_{1\le k\le n}\sigma(k)p(n-k).
</math> &nbsp; &nbsp;<ref>G.H. Hardy, S. Ramannujan, ''Asymptotic Formulæ in Combinatory Analysis'', § 1.3; in Ramannujan, ''Papers'' p. 279</ref> &nbsp; This recurrence can be used to compute ''p''(''n'').

===Class number related===
[[Biography:Peter Gustav Lejeune Dirichlet|Peter Gustav Lejeune Dirichlet]] discovered formulas that relate the class number ''h'' of quadratic number fields to the Jacobi symbol.<ref>Landau, p. 168, credits Gauss as well as Dirichlet</ref>

An integer ''D'' is called a '''fundamental discriminant''' if it is the [[Discriminant|discriminant]] of a quadratic number field. This is equivalent to ''D'' ≠  1 and either a) ''D'' is squarefree and ''D'' ≡ 1 (mod 4) or b) ''D'' ≡ 0 (mod 4), ''D''/4  is squarefree, and ''D''/4 ≡ 2 or 3 (mod 4).<ref>Cohen, Def. 5.1.2</ref>

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the [[Kronecker symbol]]:
<math display="block">\left(\frac{a}{2}\right) = \begin{cases}
\;\;\,0&\text{ if } a \text{ is even}
\\(-1)^{\frac{a^2-1}{8}}&\text{ if }a \text{ is odd. }
\end{cases}</math>

Then if ''D'' < −4 is a fundamental discriminant<ref>Cohen, Corr. 5.3.13</ref><ref>see Edwards, § 9.5 exercises for more complicated formulas.</ref>
<math display="block">\begin{align}
h(D) & = \frac{1}{D} \sum_{r=1}^{|D|}r\left(\frac{D}{r}\right)\\
     & = \frac{1}{2-\left(\tfrac{D}{2}\right)} \sum_{r=1}^{|D|/2}\left(\frac{D}{r}\right).
\end{align}</math>

There is also a formula relating ''r''<sub>3</sub> and ''h''. Again, let ''D'' be a fundamental discriminant, ''D'' < −4. Then<ref>Cohen, Prop 5.3.10</ref>
<math display="block">r_3(|D|) = 12\left(1-\left(\frac{D}{2}\right)\right)h(D).</math>

===Prime-count related===
Let <math>H_n = 1 + \frac 1 2 + \frac 1 3 + \cdots +\frac{1}{n}</math> &nbsp; be the ''n''th [[Harmonic number|harmonic number]]. Then

:<math> \sigma(n) \le H_n + e^{H_n}\log H_n</math> &nbsp; is true for every natural number ''n'' if and only if the [[Riemann hypothesis]] is true. &nbsp; &nbsp;<ref>See [[Divisor function#Growth rate|Divisor function]].</ref>

The Riemann hypothesis is also equivalent to the statement that, for all ''n'' > 5040,
<math display="block">\sigma(n) < e^\gamma n \log \log n </math> (where γ is the [[Euler–Mascheroni constant]]). This is [[Divisor function#Growth rate|Robin's theorem]].

:<math>\sum_{p}\nu_p(n) = \Omega(n).</math>
:<math>\psi(x)=\sum_{n\le x}\Lambda(n).</math> &nbsp; &nbsp;<ref>Hardy & Wright, eq. 22.1.2</ref>
:<math>\Pi(x)= \sum_{n\le x}\frac{\Lambda(n)}{\log n}.</math> &nbsp; &nbsp;<ref>See [[Prime-counting function#Other prime-counting functions|prime-counting functions]].</ref>
:<math>e^{\theta(x)}=\prod_{p\le x}p.</math> &nbsp; &nbsp;<ref>Hardy & Wright, eq. 22.1.1</ref>
:<math>e^{\psi(x)}= \operatorname{lcm}[1,2,\dots,\lfloor x\rfloor].</math> &nbsp; &nbsp;<ref>Hardy & Wright, eq. 22.1.3</ref>

===Menon's identity===
In 1965 P Kesava Menon proved<ref>László Tóth, ''Menon's Identity and Arithmetical Sums ...'', eq. 1</ref>
<math display="block">\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} \gcd(k-1,n)=\varphi(n)d(n).</math>

This has been generalized by a number of mathematicians. For example,
* B. Sury<ref>Tóth, eq. 5</ref> <math display="block">
\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,n)=1}} \gcd(k_1-1,k_2,\dots,k_s,n)
= \varphi(n)\sigma_{s-1}(n).</math>
* N. Rao<ref>Tóth, eq. 3</ref> <math display="block">
\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,k_2,\dots,k_s,n)=1}} \gcd(k_1-a_1,k_2-a_2,\dots,k_s-a_s,n)^s
=J_s(n)d(n), </math> where ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''s''</sub> are integers, gcd(''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''s''</sub>, ''n'') = 1.
*[[Biography:László Fejes Tóth|László Fejes Tóth]]<ref>Tóth, eq. 35</ref> <math display="block">
\sum_{\stackrel{1\le k\le m}{ \gcd(k,m)=1}} \gcd(k^2-1,m_1)\gcd(k^2-1,m_2)
=\varphi(n)\sum_{\stackrel{d_1\mid m_1} {d_2\mid m_2}} \varphi(\gcd(d_1, d_2))2^{\omega(\operatorname{lcm}(d_1, d_2))},
</math> where ''m''<sub>1</sub> and ''m''<sub>2</sub> are odd, ''m'' = lcm(''m''<sub>1</sub>, ''m''<sub>2</sub>).

In fact, if ''f'' is any arithmetical function<ref>Tóth, eq. 2</ref><ref>Tóth states that Menon proved this for multiplicative ''f'' in 1965 and V. Sita Ramaiah for general ''f''.</ref>
<math display="block">\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} f(\gcd(k-1,n))
=\varphi(n)\sum_{d\mid n}\frac{(\mu*f)(d)}{\varphi(d)},</math>
where <math>*</math> stands for Dirichlet convolution.

===Miscellaneous===
Let ''m'' and ''n'' be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of [[Quadratic reciprocity|quadratic reciprocity]]:
<math display="block"> \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4}.</math>

Let ''D''(''n'') be the arithmetic derivative. Then the logarithmic derivative <math display="block">\frac{D(n)}{n} = \sum_{\stackrel{p\mid n}{p\text{ prime}}} \frac {v_{p}(n)} {p}.</math> See [[Arithmetic derivative]] for details.

Let ''λ''(''n'') be Liouville's function. Then

:<math>|\lambda(n)|\mu(n) =\lambda(n)|\mu(n)| = \mu(n),</math> &nbsp; &nbsp; and
:<math>\lambda(n)\mu(n) = |\mu(n)| =\mu^2(n).</math> &nbsp; &nbsp;

Let ''λ''(''n'') be Carmichael's function. Then

:<math>\lambda(n)\mid \phi(n).</math>  &nbsp; &nbsp;  Further,

:<math>\lambda(n)= \phi(n) \text{ if and only if }n=\begin{cases}
1,2, 4;\\
3,5,7,9,11, \ldots \text{ (that is, } p^k \text{, where }p\text{ is an odd prime)};\\
6,10,14,18,\ldots \text{ (that is, } 2p^k\text{, where }p\text{ is an odd prime)}.
\end{cases}</math> 
See [[Multiplicative group of integers modulo n]] and [[Primitive root modulo n]].
&nbsp;
:<math>2^{\omega(n)} \le d(n) \le 2^{\Omega(n)}.</math> &nbsp; &nbsp;<ref>Hardy ''Ramanujan'', eq. 3.10.3</ref><ref>Hardy & Wright, § 22.13</ref>

:<math>\frac{6}{\pi^2}<\frac{\phi(n)\sigma(n)}{n^2} < 1.</math> &nbsp; &nbsp;<ref>Hardy & Wright, Thm. 329</ref>

:<math>\begin{align}
c_q(n)
&=\frac{\mu\left(\frac{q}{\gcd(q, n)}\right)}{\phi\left(\frac{q}{\gcd(q, n)}\right)}\phi(q)\\
&=\sum_{\delta\mid \gcd(q,n)}\mu\left(\frac{q}{\delta}\right)\delta.
\end{align}</math> &nbsp; &nbsp;<ref>Hardy & Wright, Thms. 271, 272</ref> &nbsp; &nbsp; Note that &nbsp;<math>\phi(q) = \sum_{\delta\mid q}\mu\left(\frac{q}{\delta}\right)\delta.</math> &nbsp; &nbsp;<ref>Hardy & Wright, eq. 16.3.1</ref>

:<math>c_q(1) = \mu(q).</math>
:<math>c_q(q) = \phi(q).</math>

:<math>\sum_{\delta\mid n}d^{3}(\delta) = \left(\sum_{\delta\mid n}d(\delta)\right)^2.</math> &nbsp; &nbsp;<ref>Ramanujan, ''Some Formulæ in the Analytic Theory of Numbers'', eq. (C); ''Papers'' p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.</ref> &nbsp; Compare this with {{math|1=1<sup>3</sup> + 2<sup>3</sup> + 3<sup>3</sup> + ... + ''n''<sup>3</sup> = (1 + 2 + 3 + ... + ''n'')<sup>2</sup>}}

:<math>d(uv) = \sum_{\delta\mid \gcd(u,v)}\mu(\delta)d\left(\frac{u}{\delta}\right)d\left(\frac{v}{\delta}\right).
</math> &nbsp; &nbsp;<ref>Ramanujan, ''Some Formulæ in the Analytic Theory of Numbers'', eq. (F); ''Papers'' p. 134</ref>

:<math>\sigma_k(u)\sigma_k(v) = \sum_{\delta\mid \gcd(u,v)}\delta^k\sigma_k\left(\frac{uv}{\delta^2}\right).
</math>  &nbsp; &nbsp;<ref>Apostol, ''Modular Functions ...'', ch. 6 eq. 4</ref>

:<math>\tau(u)\tau(v) = \sum_{\delta\mid \gcd(u,v)}\delta^{11}\tau\left(\frac{uv}{\delta^2}\right),
</math>  &nbsp; &nbsp; where ''τ''(''n'') is Ramanujan's function.  &nbsp; &nbsp;<ref>Apostol, ''Modular Functions ...'', ch. 6 eq. 3</ref>

== First 100 values of some arithmetic functions ==
{| class="wikitable"  style="text-align:right;"
! ''n''!!factorization !! {{phi}}(''n'') !! ''ω''(''n'') !! Ω(''n'') !! {{lambda}}(''n'') !! {{mu}}(''n'') !! {{lambda|uc=true}}(''n'') !! {{pi}}(''n'')!! {{sigma}}<sub>0</sub>(''n'')!! {{sigma}}<sub>1</sub>(''n'')!! {{sigma}}<sub>2</sub>(''n'')!! ''r''<sub>2</sub>(''n'')!! ''r''<sub>3</sub>(''n'')!! ''r''<sub>4</sub>(''n'')
|-
| 1||style='text-align:center;'| 1|| 1|| 0|| 0|| 1|| 1|| 0|| 0|| 1|| 1|| 1|| 4|| 6|| 8
|-style="background-color:#ddeeff;"
| 2||style='text-align:center;'| 2|| 1|| 1|| 1|| −1|| −1|| 0.69|| 1|| 2|| 3|| 5|| 4|| 12|| 24
|-style="background-color:#ddeeff;"
| 3||style='text-align:center;'| 3|| 2|| 1|| 1|| −1|| −1|| 1.10|| 2|| 2|| 4|| 10|| 0|| 8|| 32
|-
| 4||style='text-align:center;'| 2<sup>2</sup>|| 2|| 1|| 2|| 1|| 0|| 0.69|| 2|| 3|| 7|| 21|| 4|| 6|| 24
|-style="background-color:#ddeeff;"
| 5||style='text-align:center;'| 5|| 4|| 1|| 1|| −1|| −1|| 1.61|| 3|| 2|| 6|| 26|| 8|| 24|| 48
|-
| 6||style='text-align:center;'| 2 · 3|| 2|| 2|| 2|| 1|| 1|| 0|| 3|| 4|| 12|| 50|| 0|| 24|| 96
|-style="background-color:#ddeeff;"
| 7||style='text-align:center;'| 7|| 6|| 1|| 1|| −1|| −1|| 1.95|| 4|| 2|| 8|| 50|| 0|| 0|| 64
|-
| 8||style='text-align:center;'| 2<sup>3</sup>|| 4|| 1|| 3|| −1|| 0|| 0.69|| 4|| 4|| 15|| 85|| 4|| 12|| 24
|-
| 9||style='text-align:center;'| 3<sup>2</sup>|| 6|| 1|| 2|| 1|| 0|| 1.10|| 4|| 3|| 13|| 91|| 4|| 30|| 104
|-
| 10||style='text-align:center;'| 2 · 5|| 4|| 2|| 2|| 1|| 1|| 0|| 4|| 4|| 18|| 130|| 8|| 24|| 144
|-style="background-color:#ddeeff;"
| 11||style='text-align:center;'| 11|| 10|| 1|| 1|| −1|| −1|| 2.40|| 5|| 2|| 12|| 122|| 0|| 24|| 96
|-
| 12||style='text-align:center;'| 2<sup>2</sup> · 3|| 4|| 2|| 3|| −1|| 0|| 0|| 5|| 6|| 28|| 210|| 0|| 8|| 96
|-style="background-color:#ddeeff;"
| 13||style='text-align:center;'| 13|| 12|| 1|| 1|| −1|| −1|| 2.56|| 6|| 2|| 14|| 170|| 8|| 24|| 112
|-
| 14||style='text-align:center;'| 2 · 7|| 6|| 2|| 2|| 1|| 1|| 0|| 6|| 4|| 24|| 250|| 0|| 48|| 192
|-
| 15||style='text-align:center;'| 3 · 5|| 8|| 2|| 2|| 1|| 1|| 0|| 6|| 4|| 24|| 260|| 0|| 0|| 192
|-
| 16||style='text-align:center;'| 2<sup>4</sup>|| 8|| 1|| 4|| 1|| 0|| 0.69|| 6|| 5|| 31|| 341|| 4|| 6|| 24
|-style="background-color:#ddeeff;"
| 17||style='text-align:center;'| 17|| 16|| 1|| 1|| −1|| −1|| 2.83|| 7|| 2|| 18|| 290|| 8|| 48|| 144
|-
| 18||style='text-align:center;'| 2 · 3<sup>2</sup>|| 6|| 2|| 3|| −1|| 0|| 0|| 7|| 6|| 39|| 455|| 4|| 36|| 312
|-style="background-color:#ddeeff;"
| 19||style='text-align:center;'| 19|| 18|| 1|| 1|| −1|| −1|| 2.94|| 8|| 2|| 20|| 362|| 0|| 24|| 160
|-
| 20||style='text-align:center;'| 2<sup>2</sup> · 5|| 8|| 2|| 3|| −1|| 0|| 0|| 8|| 6|| 42|| 546|| 8|| 24|| 144
|-
| 21||style='text-align:center;'| 3 · 7|| 12|| 2|| 2|| 1|| 1|| 0|| 8|| 4|| 32|| 500|| 0|| 48|| 256
|-
| 22||style='text-align:center;'| 2 · 11|| 10|| 2|| 2|| 1|| 1|| 0|| 8|| 4|| 36|| 610|| 0|| 24|| 288
|-style="background-color:#ddeeff;"
| 23||style='text-align:center;'| 23|| 22|| 1|| 1|| −1|| −1|| 3.14|| 9|| 2|| 24|| 530|| 0|| 0|| 192
|-
| 24||style='text-align:center;'| 2<sup>3</sup> · 3|| 8|| 2|| 4|| 1|| 0|| 0|| 9|| 8|| 60|| 850|| 0|| 24|| 96
|-
| 25||style='text-align:center;'| 5<sup>2</sup>|| 20|| 1|| 2|| 1|| 0|| 1.61|| 9|| 3|| 31|| 651|| 12|| 30|| 248
|-
| 26||style='text-align:center;'| 2 · 13|| 12|| 2|| 2|| 1|| 1|| 0|| 9|| 4|| 42|| 850|| 8|| 72|| 336
|-
| 27||style='text-align:center;'| 3<sup>3</sup>|| 18|| 1|| 3|| −1|| 0|| 1.10|| 9|| 4|| 40|| 820|| 0|| 32|| 320
|-
| 28||style='text-align:center;'| 2<sup>2</sup> · 7|| 12|| 2|| 3|| −1|| 0|| 0|| 9|| 6|| 56|| 1050|| 0|| 0|| 192
|-style="background-color:#ddeeff;"
| 29||style='text-align:center;'| 29|| 28|| 1|| 1|| −1|| −1|| 3.37|| 10|| 2|| 30|| 842|| 8|| 72|| 240
|-
| 30||style='text-align:center;'| 2 · 3 · 5|| 8|| 3|| 3|| −1|| −1|| 0|| 10|| 8|| 72|| 1300|| 0|| 48|| 576
|-style="background-color:#ddeeff;"
| 31||style='text-align:center;'| 31|| 30|| 1|| 1|| −1|| −1|| 3.43|| 11|| 2|| 32|| 962|| 0|| 0|| 256
|-
| 32||style='text-align:center;'| 2<sup>5</sup>|| 16|| 1|| 5|| −1|| 0|| 0.69|| 11|| 6|| 63|| 1365|| 4|| 12|| 24
|-
| 33||style='text-align:center;'| 3 · 11|| 20|| 2|| 2|| 1|| 1|| 0|| 11|| 4|| 48|| 1220|| 0|| 48|| 384
|-
| 34||style='text-align:center;'| 2 · 17|| 16|| 2|| 2|| 1|| 1|| 0|| 11|| 4|| 54|| 1450|| 8|| 48|| 432
|-
| 35||style='text-align:center;'| 5 · 7|| 24|| 2|| 2|| 1|| 1|| 0|| 11|| 4|| 48|| 1300|| 0|| 48|| 384
|-
| 36||style='text-align:center;'| 2<sup>2</sup> · 3<sup>2</sup>|| 12|| 2|| 4|| 1|| 0|| 0|| 11|| 9|| 91|| 1911|| 4|| 30|| 312
|-style="background-color:#ddeeff;"
| 37||style='text-align:center;'| 37|| 36|| 1|| 1|| −1|| −1|| 3.61|| 12|| 2|| 38|| 1370|| 8|| 24|| 304
|-
| 38||style='text-align:center;'| 2 · 19|| 18|| 2|| 2|| 1|| 1|| 0|| 12|| 4|| 60|| 1810|| 0|| 72|| 480
|-
| 39||style='text-align:center;'| 3 · 13|| 24|| 2|| 2|| 1|| 1|| 0|| 12|| 4|| 56|| 1700|| 0|| 0|| 448
|-
| 40||style='text-align:center;'| 2<sup>3</sup> · 5|| 16|| 2|| 4|| 1|| 0|| 0|| 12|| 8|| 90|| 2210|| 8|| 24|| 144
|-style="background-color:#ddeeff;"
| 41||style='text-align:center;'| 41|| 40|| 1|| 1|| −1|| −1|| 3.71|| 13|| 2|| 42|| 1682|| 8|| 96|| 336
|-
| 42||style='text-align:center;'| 2 · 3 · 7|| 12|| 3|| 3|| −1|| −1|| 0|| 13|| 8|| 96|| 2500|| 0|| 48|| 768
|-style="background-color:#ddeeff;"
| 43||style='text-align:center;'| 43|| 42|| 1|| 1|| −1|| −1|| 3.76|| 14|| 2|| 44|| 1850|| 0|| 24|| 352
|-
| 44||style='text-align:center;'| 2<sup>2</sup> · 11|| 20|| 2|| 3|| −1|| 0|| 0|| 14|| 6|| 84|| 2562|| 0|| 24|| 288
|-
| 45||style='text-align:center;'| 3<sup>2</sup> · 5|| 24|| 2|| 3|| −1|| 0|| 0|| 14|| 6|| 78|| 2366|| 8|| 72|| 624
|-
| 46||style='text-align:center;'| 2 · 23|| 22|| 2|| 2|| 1|| 1|| 0|| 14|| 4|| 72|| 2650|| 0|| 48|| 576
|-style="background-color:#ddeeff;"
| 47||style='text-align:center;'| 47|| 46|| 1|| 1|| −1|| −1|| 3.85|| 15|| 2|| 48|| 2210|| 0|| 0|| 384
|-
| 48||style='text-align:center;'| 2<sup>4</sup> · 3|| 16|| 2|| 5|| −1|| 0|| 0|| 15|| 10|| 124|| 3410|| 0|| 8|| 96
|-
| 49||style='text-align:center;'| 7<sup>2</sup>|| 42|| 1|| 2|| 1|| 0|| 1.95|| 15|| 3|| 57|| 2451|| 4|| 54|| 456
|-
| 50||style='text-align:center;'| 2 · 5<sup>2</sup>|| 20|| 2|| 3|| −1|| 0|| 0|| 15|| 6|| 93|| 3255|| 12|| 84|| 744
|-
| 51||style='text-align:center;'| 3 · 17|| 32|| 2|| 2|| 1|| 1|| 0|| 15|| 4|| 72|| 2900|| 0|| 48|| 576
|-
| 52||style='text-align:center;'| 2<sup>2</sup> · 13|| 24|| 2|| 3|| −1|| 0|| 0|| 15|| 6|| 98|| 3570|| 8|| 24|| 336
|-style="background-color:#ddeeff;"
| 53||style='text-align:center;'| 53|| 52|| 1|| 1|| −1|| −1|| 3.97|| 16|| 2|| 54|| 2810|| 8|| 72|| 432
|-
| 54||style='text-align:center;'| 2 · 3<sup>3</sup>|| 18|| 2|| 4|| 1|| 0|| 0|| 16|| 8|| 120|| 4100|| 0|| 96|| 960
|-
| 55||style='text-align:center;'| 5 · 11|| 40|| 2|| 2|| 1|| 1|| 0|| 16|| 4|| 72|| 3172|| 0|| 0|| 576
|-
| 56||style='text-align:center;'| 2<sup>3</sup> · 7|| 24|| 2|| 4|| 1|| 0|| 0|| 16|| 8|| 120|| 4250|| 0|| 48|| 192
|-
| 57||style='text-align:center;'| 3 · 19|| 36|| 2|| 2|| 1|| 1|| 0|| 16|| 4|| 80|| 3620|| 0|| 48|| 640
|-
| 58||style='text-align:center;'| 2 · 29|| 28|| 2|| 2|| 1|| 1|| 0|| 16|| 4|| 90|| 4210|| 8|| 24|| 720
|-style="background-color:#ddeeff;"
| 59||style='text-align:center;'| 59|| 58|| 1|| 1|| −1|| −1|| 4.08|| 17|| 2|| 60|| 3482|| 0|| 72|| 480
|-
| 60||style='text-align:center;'| 2<sup>2</sup> · 3 · 5|| 16|| 3|| 4|| 1|| 0|| 0|| 17|| 12|| 168|| 5460|| 0|| 0|| 576
|-style="background-color:#ddeeff;"
| 61||style='text-align:center;'| 61|| 60|| 1|| 1|| −1|| −1|| 4.11|| 18|| 2|| 62|| 3722|| 8|| 72|| 496
|-
| 62||style='text-align:center;'| 2 · 31|| 30|| 2|| 2|| 1|| 1|| 0|| 18|| 4|| 96|| 4810|| 0|| 96|| 768
|-
| 63||style='text-align:center;'| 3<sup>2</sup> · 7|| 36|| 2|| 3|| −1|| 0|| 0|| 18|| 6|| 104|| 4550|| 0|| 0|| 832
|-
| 64||style='text-align:center;'| 2<sup>6</sup>|| 32|| 1|| 6|| 1|| 0|| 0.69|| 18|| 7|| 127|| 5461|| 4|| 6|| 24
|-
| 65||style='text-align:center;'| 5 · 13|| 48|| 2|| 2|| 1|| 1|| 0|| 18|| 4|| 84|| 4420|| 16|| 96|| 672
|-
| 66||style='text-align:center;'| 2 · 3 · 11|| 20|| 3|| 3|| −1|| −1|| 0|| 18|| 8|| 144|| 6100|| 0|| 96|| 1152
|-style="background-color:#ddeeff;"
| 67||style='text-align:center;'| 67|| 66|| 1|| 1|| −1|| −1|| 4.20|| 19|| 2|| 68|| 4490|| 0|| 24|| 544
|-
| 68||style='text-align:center;'| 2<sup>2</sup> · 17|| 32|| 2|| 3|| −1|| 0|| 0|| 19|| 6|| 126|| 6090|| 8|| 48|| 432
|-
| 69||style='text-align:center;'| 3 · 23|| 44|| 2|| 2|| 1|| 1|| 0|| 19|| 4|| 96|| 5300|| 0|| 96|| 768
|-
| 70||style='text-align:center;'| 2 · 5 · 7|| 24|| 3|| 3|| −1|| −1|| 0|| 19|| 8|| 144|| 6500|| 0|| 48|| 1152
|-style="background-color:#ddeeff;"
| 71||style='text-align:center;'| 71|| 70|| 1|| 1|| −1|| −1|| 4.26|| 20|| 2|| 72|| 5042|| 0|| 0|| 576
|-
| 72||style='text-align:center;'| 2<sup>3</sup> · 3<sup>2</sup>|| 24|| 2|| 5|| −1|| 0|| 0|| 20|| 12|| 195|| 7735|| 4|| 36|| 312
|-style="background-color:#ddeeff;"
| 73||style='text-align:center;'| 73|| 72|| 1|| 1|| −1|| −1|| 4.29|| 21|| 2|| 74|| 5330|| 8|| 48|| 592
|-
| 74||style='text-align:center;'| 2 · 37|| 36|| 2|| 2|| 1|| 1|| 0|| 21|| 4|| 114|| 6850|| 8|| 120|| 912
|-
| 75||style='text-align:center;'| 3 · 5<sup>2</sup>|| 40|| 2|| 3|| −1|| 0|| 0|| 21|| 6|| 124|| 6510|| 0|| 56|| 992
|-
| 76||style='text-align:center;'| 2<sup>2</sup> · 19|| 36|| 2|| 3|| −1|| 0|| 0|| 21|| 6|| 140|| 7602|| 0|| 24|| 480
|-
| 77||style='text-align:center;'| 7 · 11|| 60|| 2|| 2|| 1|| 1|| 0|| 21|| 4|| 96|| 6100|| 0|| 96|| 768
|-
| 78||style='text-align:center;'| 2 · 3 · 13|| 24|| 3|| 3|| −1|| −1|| 0|| 21|| 8|| 168|| 8500|| 0|| 48|| 1344
|-style="background-color:#ddeeff;"
| 79||style='text-align:center;'| 79|| 78|| 1|| 1|| −1|| −1|| 4.37|| 22|| 2|| 80|| 6242|| 0|| 0|| 640
|-
| 80||style='text-align:center;'| 2<sup>4</sup> · 5|| 32|| 2|| 5|| −1|| 0|| 0|| 22|| 10|| 186|| 8866|| 8|| 24|| 144
|-
| 81||style='text-align:center;'| 3<sup>4</sup>|| 54|| 1|| 4|| 1|| 0|| 1.10|| 22|| 5|| 121|| 7381|| 4|| 102|| 968
|-
| 82||style='text-align:center;'| 2 · 41|| 40|| 2|| 2|| 1|| 1|| 0|| 22|| 4|| 126|| 8410|| 8|| 48|| 1008
|-style="background-color:#ddeeff;"
| 83||style='text-align:center;'| 83|| 82|| 1|| 1|| −1|| −1|| 4.42|| 23|| 2|| 84|| 6890|| 0|| 72|| 672
|-
| 84||style='text-align:center;'| 2<sup>2</sup> · 3 · 7|| 24|| 3|| 4|| 1|| 0|| 0|| 23|| 12|| 224|| 10500|| 0|| 48|| 768
|-
| 85||style='text-align:center;'| 5 · 17|| 64|| 2|| 2|| 1|| 1|| 0|| 23|| 4|| 108|| 7540|| 16|| 48|| 864
|-
| 86||style='text-align:center;'| 2 · 43|| 42|| 2|| 2|| 1|| 1|| 0|| 23|| 4|| 132|| 9250|| 0|| 120|| 1056
|-
| 87||style='text-align:center;'| 3 · 29|| 56|| 2|| 2|| 1|| 1|| 0|| 23|| 4|| 120|| 8420|| 0|| 0|| 960
|-
| 88||style='text-align:center;'| 2<sup>3</sup> · 11|| 40|| 2|| 4|| 1|| 0|| 0|| 23|| 8|| 180|| 10370|| 0|| 24|| 288
|-style="background-color:#ddeeff;"
| 89||style='text-align:center;'| 89|| 88|| 1|| 1|| −1|| −1|| 4.49|| 24|| 2|| 90|| 7922|| 8|| 144|| 720
|-
| 90||style='text-align:center;'| 2 · 3<sup>2</sup> · 5|| 24|| 3|| 4|| 1|| 0|| 0|| 24|| 12|| 234|| 11830|| 8|| 120|| 1872
|-
| 91||style='text-align:center;'| 7 · 13|| 72|| 2|| 2|| 1|| 1|| 0|| 24|| 4|| 112|| 8500|| 0|| 48|| 896
|-
| 92||style='text-align:center;'| 2<sup>2</sup> · 23|| 44|| 2|| 3|| −1|| 0|| 0|| 24|| 6|| 168|| 11130|| 0|| 0|| 576
|-
| 93||style='text-align:center;'| 3 · 31|| 60|| 2|| 2|| 1|| 1|| 0|| 24|| 4|| 128|| 9620|| 0|| 48|| 1024
|-
| 94||style='text-align:center;'| 2 · 47|| 46|| 2|| 2|| 1|| 1|| 0|| 24|| 4|| 144|| 11050|| 0|| 96|| 1152
|-
| 95||style='text-align:center;'| 5 · 19|| 72|| 2|| 2|| 1|| 1|| 0|| 24|| 4|| 120|| 9412|| 0|| 0|| 960
|-
| 96||style='text-align:center;'| 2<sup>5</sup> · 3|| 32|| 2|| 6|| 1|| 0|| 0|| 24|| 12|| 252|| 13650|| 0|| 24|| 96
|-style="background-color:#ddeeff;"
| 97||style='text-align:center;'| 97|| 96|| 1|| 1|| −1|| −1|| 4.57|| 25|| 2|| 98|| 9410|| 8|| 48|| 784
|-
| 98||style='text-align:center;'| 2 · 7<sup>2</sup>|| 42|| 2|| 3|| −1|| 0|| 0|| 25|| 6|| 171|| 12255|| 4|| 108|| 1368
|-
| 99||style='text-align:center;'| 3<sup>2</sup> · 11|| 60|| 2|| 3|| −1|| 0|| 0|| 25|| 6|| 156|| 11102|| 0|| 72|| 1248
|-
| 100||style='text-align:center;'| 2<sup>2</sup> · 5<sup>2</sup>|| 40|| 2|| 4|| 1|| 0|| 0|| 25|| 9|| 217|| 13671|| 12|| 30|| 744
|-
! ''n''!!factorization !! {{phi}}(''n'') !! ''&omega;''(''n'') !! &Omega;(''n'') !! {{lambda}}(''n'') !! {{mu}}(''n'') !! {{lambda|uc=true}}(''n'') !! {{pi}}(''n'')!! {{sigma}}<sub>0</sub>(''n'')!! {{sigma}}<sub>1</sub>(''n'')!! {{sigma}}<sub>2</sub>(''n'')!! ''r''<sub>2</sub>(''n'')!! ''r''<sub>3</sub>(''n'')!! ''r''<sub>4</sub>(''n'')

|}

==Notes==
{{Reflist|30em}}

== References ==
* {{Citation
|title=Introduction to Analytic Number Theory
|author=Tom M. Apostol
|year=1976
|publisher=Springer [[Undergraduate Texts in Mathematics]]
|isbn=0-387-90163-9
|url-access=registration
|url=https://archive.org/details/introductiontoan00apos_0
}}
* {{Citation |last       = Apostol
 |first      = Tom M.
 |title      = Modular Functions and Dirichlet Series in Number Theory (2nd Edition)
 |publisher  = Springer
 |location   = New York
 |year       = 1989
 |isbn       = 0-387-97127-0
 |url-access = registration
 |url        = https://archive.org/details/modularfunctions0000apos
}}
* {{citation | first1 = Paul T. | last1 = Bateman | first2 = Harold G. | last2 = Diamond | year = 2004 | title = Analytic number theory, an introduction | publisher = [[Company:World Scientific|World Scientific]]  | isbn = 978-981-238-938-1 }}
* {{citation
  | title = A Course in Computational Algebraic Number Theory
  | publisher = [[Company:Springer Nature|Springer]]
  | location = Berlin
  | year = 1993
  | isbn = 3-540-55640-0}}
* {{cite book
  | last = Edwards
  | first = Harold
  | title = Fermat's Last Theorem
  | publisher = [[Company:Springer Nature|Springer]]
  | location = New York
  | year = 1977
  | isbn = 0-387-90230-9}}
* {{Citation
  | last1 = Hardy  | first1 = G. H.
  | title = Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work
  | publisher = AMS / Chelsea
  | location = Providence RI
  | year = 1999
  | isbn = 978-0-8218-2023-0| hdl = 10115/1436
  }}
* {{Hardy and Wright|edition=5th}}
* {{Citation
|title=The Prime Number Theorem
|first=G. J. O. | last=Jameson
|year=2003
|publisher=Cambridge University Press
|isbn=0-521-89110-8}}
* {{Citation
  | last1 = Koblitz | first1 = Neal
  | title = Introduction to Elliptic Curves and Modular Forms
  | publisher = Springer
  | location = New York
  | year = 1984
  | isbn = 0-387-97966-2}}
* {{citation
  | title = Elementary Number Theory
  | publisher = Chelsea
  | location = New York
  | year = 1966}}
* {{Citation
|title=Fundamentals of Number Theory
|author=William J. LeVeque
|year=1996
|publisher=Courier Dover Publications
|isbn=0-486-68906-9}}
* {{citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = [[Software:D. C. Heath and Company|D. C. Heath and Company]] | location = Lexington | lccn = 77-171950 }}
* {{Citation
|title=Introduction to Mathematical Logic
|author=Elliott Mendelson
|year=1987
|publisher=CRC Press
|isbn=0-412-80830-7}}
*{{citation
  | title = Introduction to number theory (2nd Edition)
  | publisher = Chelsea
  | year = 1964
  | isbn = 978-0-8218-2833-5}}
* {{citation | first1 = Ivan M. | last1 = Niven| first2 = Herbert S. | last2 = Zuckerman | year = 1972 | title = An introduction to the theory of numbers (3rd Edition) | publisher = {{wipe|John Wiley & Sons}}  | isbn = 0-471-64154-5 }}
* {{citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = Prentice Hall | location = Englewood Cliffs | lccn = 77-81766 }}
* {{Citation
  | last1 = Ramanujan  | first1 = Srinivasa
  | title = Collected Papers
  | publisher = AMS / Chelsea
  | location = Providence RI
  | year = 2000
  | isbn = 978-0-8218-2076-6}}
* {{citation | last=Williams | first=Kenneth S. | title=Number theory in the spirit of Liouville | zbl=1227.11002 | series=London Mathematical Society Student Texts | volume=76 | location=Cambridge | publisher={{wipe|Cambridge University Press}} | isbn=978-0-521-17562-3 | year=2011 }}

==Further reading==
* {{citation | first1=Wolfgang | last1=Schwarz | first2=Jürgen | last2=Spilker | title=Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties | year=1994 | publisher={{wipe|Cambridge University Press}} | isbn=0-521-42725-8 | zbl=0807.11001 | series=London Mathematical Society Lecture Note Series | volume=184 }}

==External links==
* {{springer|title=Arithmetic function|id=p/a013300}}
* Matthew Holden, Michael Orrison, Michael Varble [https://web.archive.org/web/20160305132124/https://www.math.hmc.edu/~orrison/research/papers/totient.pdf Yet another Generalization of Euler's Totient Function]
* Huard, Ou, Spearman, and Williams. [http://mathstat.carleton.ca/~williams/papers/pdf/249.pdf Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions] 
* Dineva, Rosica, [http://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf The Euler Totient, the Möbius, and the Divisor Functions] {{Webarchive|url=https://web.archive.org/web/20210116061553/https://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf |date=2021-01-16 }}
* László  Tóth, [https://arxiv.org/PS_cache/arxiv/pdf/1103/1103.5861v2.pdf Menon's Identity and arithmetical sums representing functions of several variables]

{{Classes of natural numbers|collapsed}}


[[Category:Arithmetic functions| ]]
[[Category:Functions and mappings]]

{{Sourceattribution|Arithmetic function}}