Editing Arithmetic function (section)

== 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]] 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 number related|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]] 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 ===
[[Peter Gustav Lejeune Dirichlet]] discovered formulas that relate the class number ''h'' of [[quadratic number field]]s 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]] 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]]. 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.
* [[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]]:
<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>