Famous Theorems of Mathematics/Number Theory/Totient Function

This page provides proofs for identities involving the totient function $\varphi (k)$ and the Möbius function $\mu (k)$.

Sum of integers relatively prime to and less than or equal to n

The proof of the identity

$\sum _{1\leq k\leq n \atop (k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 2$

uses the fact that

$(k,n)=d\quad \Leftrightarrow \quad (n-k,n)=d$

because if $d|n$ and $d|k$ then $d|n-k$ and if $d|n$ and $d|(n-k)$ then $d|n-(n-k)=k.$

This means that for $n>2$ we may group the k that are relatively prime to n into pairs

$(k,n-k)\quad {\mbox{ where }}\quad k<n-k.$.

The case $k=n/2$ does not occur because $n/2$ is not an integer when n is odd, and when n is even, we have $(n/2,n)=n/2>1$ because we assumed that $n>2.$ There are

${\frac {\varphi (n)}{2}}$

such pairs, and the constituents of each pair sum to

$k\;+\;n-k\;=n,$

hence

$\sum _{(k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 3.$

The case $n=2$ is verified by direct substitution and may be included in the formula.

Proofs of totient identities involving the floor function

The proof of the identity

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor$

is by mathematical induction on $n$. The base case is $n=1$ and we see that the claim holds:

$\varphi (1)/1=1={\frac {\mu (1)}{1}}\left\lfloor 1\right\rfloor .$

For the induction step we need to prove that

${\frac {\varphi (n+1)}{n+1}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \right)+{\frac {\mu (n+1)}{n+1}}.$

The key observation is that

$\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \;=\;{\begin{cases}1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise, }}\end{cases}}$

so that the sum is

$\sum _{k|n+1,\;k<n+1}{\frac {\mu (k)}{k}}+{\frac {\mu (n+1)}{n+1}}=\sum _{k|n+1}{\frac {\mu (k)}{k}}.$

Now the fact that

$\sum _{k|n+1}{\frac {\mu (k)}{k}}={\frac {\varphi (n+1)}{n+1}}$

is a basic totient identity. To see that it holds, let $p_{1}^{v_{1}}p_{2}^{v_{2}}\ldots p_{q}^{v_{q}}$ be the prime factorization of n+1. Then

${\frac {\varphi (n+1)}{n+1}}=\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}}}\right)=\sum _{k|n+1}{\frac {\mu (k)}{k}}$

by definition of $\mu (k).$ This concludes the proof.

An alternate proof proceeds by substituting ${\frac {\varphi (k)}{k}}=\sum _{d|k}{\frac {\mu (d)}{d}}$ directly into the left side of the identity, giving $\sum _{k=1}^{n}\sum _{d|k}{\frac {\mu (d)}{d}}.$

Now we ask how often the term ${\begin{matrix}{\frac {\mu (d)}{d}}\end{matrix}}$ occurs in the double sum. The answer is that it occurs for every multiple $k$ of $d$, but there are precisely ${\begin{matrix}\left\lfloor {\frac {n}{d}}\right\rfloor \end{matrix}}$ such multiples, which means that the sum is

$\sum _{d=1}^{n}{\frac {\mu (d)}{d}}\left\lfloor {\frac {n}{d}}\right\rfloor$

as claimed.

---

The trick where zero values of ${\begin{matrix}\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \end{matrix}}$ are filtered out may also be used to prove the identity

$\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right).$

The base case is $n=1$ and we have

$\varphi (1)=1={\frac {1}{2}}\left(1+\mu (1)\left\lfloor {\frac {1}{1}}\right\rfloor ^{2}\right)$

and it holds. The induction step requires us to show that

$\varphi (n+1)={\frac {1}{2}}\sum _{k=1}^{n}\mu (k)\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)\;+\;{\frac {1}{2}}\;\mu (n+1)\;\left\lfloor {\frac {n+1}{n+1}}\right\rfloor ^{2}.$

Next observe that

$\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\;=\;{\begin{cases}2{\frac {n+1}{k}}-1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise.}}\end{cases}}$

This gives the following for the sum

${\frac {1}{2}}\sum _{k|n+1,\;k<n+1}\mu (k)\left(2{\frac {n+1}{k}}-1\right)\;+\;{\frac {1}{2}}\;\mu (n+1)={\frac {1}{2}}\sum _{k|n+1}\mu (k)\left(2\;{\frac {n+1}{k}}-1\right).$

Treating the two inner terms separately, we get

$(n+1)\sum _{k|n+1}{\frac {\mu (k)}{k}}-{\frac {1}{2}}\sum _{k|n+1}\mu (k).$

The first of these two is precisely $\varphi (n+1)$ as we saw earlier, and the second is zero, by a basic property of the Möbius function (using the same factorization of $n+1$ as above, we have ${\begin{matrix}\sum _{k|n+1}\mu (k)=\prod _{l=1}^{q}(1-1)=0\end{matrix}}$.) This concludes the proof.

This result may also be proved by inclusion-exclusion. Rewrite the identity as

$-1+2\sum _{k=1}^{n}\varphi (k)=\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}.$

Now we see that the left side counts the number of lattice points (a, b) in [1,n] × [1,n] where a and b are relatively prime to each other. Using the sets $A_{p}$ where p is a prime less than or equal to n to denote the set of points where both coordinates are divisible by p we have

$\left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.$

This formula counts the number of pairs where a and b are not relatively prime to each other. The cardinalities are as follows:

$\left|A_{p}\right|=\left\lfloor {\frac {n}{p}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\right|=\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2},\;\ldots$

and the signs are ${\begin{matrix}-\mu (pqr\cdots )\end{matrix}}$, hence the number of points with relatively prime coordinates is

$\mu (1)\,n^{2}\;+\;\sum _{p}\mu (p)\left\lfloor {\frac {n}{p}}\right\rfloor ^{2}\;+\;\sum _{p<q}\mu (pq)\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2}\;+\;\sum _{p<q<r}\mu (pqr)\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2}\;+\;\cdots$

but this is precisely $\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}$ and we have the claim.

Average order of the totient

We will use the last formula of the preceding section to prove the following result:

${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)$

Using $x-1<\lfloor x\rfloor \leq x$ we have the upper bound

${\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k){\frac {n^{2}}{k^{2}}}\right)={\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}$

and the lower bound

${\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k)\left({\frac {n^{2}}{k^{2}}}-2{\frac {n}{k}}+1\right)\right)$

which is

${\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}+{\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)$

Working with the last two terms and using the asymptotic expansion of the nth harmonic number we have

$-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}>-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {1}{k}}=-{\frac {1}{n}}H_{n}>-{\frac {1}{n}}(\log n+1)$

and

${\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)>-{\frac {1}{2n}}.$

Now we check the order of the terms in the upper and lower bound. The term ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$ is ${\mathcal {O}}(1)$ by comparison with $\zeta (2)$, where $\zeta (s)$ is the Riemann zeta function. The next largest term is the logarithmic term from the lower bound.

So far we have shown that

${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)$

It remains to evaluate ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$ asymptotically, which we have seen converges. The Euler product for the Riemann zeta function is

$\zeta (s)=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)^{-1}{\mbox{ for }}\Re (s)>1.$

Now it follows immediately from the definition of the Möbius function that

${\frac {1}{\zeta (s)}}=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}.$

This means that

${\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}={\frac {1}{2}}{\frac {1}{\zeta (2)}}+{\mathcal {O}}\left({\frac {1}{n}}\right)$

where the integral ${\begin{matrix}\int _{n+1}^{\infty }{\frac {1}{t^{2}}}dt\end{matrix}}$ was used to estimate ${\begin{matrix}\sum _{k>n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}.$ But ${\begin{matrix}{\frac {1}{2}}{\frac {1}{\zeta (2)}}={\frac {3}{\pi ^{2}}}\end{matrix}}$ and we have established the claim.

Average order of φ(n)/n

The material of the preceding section, together with the identity

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor$

also yields a proof that

${\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {6}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right).$

Reasoning as before, we have the upper bound

${\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}{\frac {n}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}$

and the lower bound

$-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}+\sum _{k=1}^{n+1}{\frac {\mu (k)}{k^{2}}}.$

Now apply the estimates from the preceding section to obtain the result.

Inequalities

We first show that

$\lim \inf {\frac {\varphi (n)}{n}}=0{\mbox{ and }}\lim \sup {\frac {\varphi (n)}{n}}=1.$

The latter holds because when n is a power of a prime p, we have

${\frac {\varphi (n)}{n}}=1-{\frac {1}{p}},$

which gets arbitrarily close to 1 for p large enough (and we can take p as large as we please since there are infinitely many primes).

To see the former, let n_k be the product of the first k primes, call them $p_{1},p_{2},...,p_{k}$. Let

$r_{k}={\frac {\varphi (n_{k})}{n_{k}}}=\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).$

Then

${\frac {1}{r_{k}}}=\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right)^{-1}>\sum _{m=1}^{p_{k}}{\frac {1}{m}}=H_{p_{k}},$

a harmonic number. Hence, by the well-known bound $H_{n}>\log n$, we have

${\frac {1}{r_{k}}}>\log p_{k}.$

Since the logarithm is unbounded, taking k arbitrarily large ensures that r_k achieves values arbitrarily close to zero.

We use the same factorization of n as in the first section to prove that

${\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}$.

Note that

$\varphi (n)\sigma (n)=n\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}}}\right)\prod _{l=1}^{q}{\frac {p_{l}^{v_{l}+1}-1}{p_{l}-1}}=n\prod _{l=1}^{q}{\frac {p_{l}-1}{p_{l}}}\;{\frac {p_{l}^{v_{l}+1}-1}{p_{l}-1}}$

which is

$n\prod _{l=1}^{q}\left(p_{l}^{v_{l}}-{\frac {1}{p_{l}}}\right)=n^{2}\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right).$

The upper bound follows immediately since

$\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right)<1.$

We come arbitrarily close to this bound when n is prime. For the lower bound, note that

$\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right)\geq \prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{2}}}\right)>\prod _{p}\left(1-{\frac {1}{p^{2}}}\right),$

where the product is over all primes. We have already seen this product, as in

$\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}$

so that

$\prod _{p}\left(1-{\frac {1}{p^{2}}}\right)={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}$

and we have the claim. The values of n that come closest to this bound are products of the first k primes.

External links

• Chris K. Caldwell, What is the probability that gcd(n,m)=1?
• Bordellès, Olivier, Numbers prime to q in $[1,n]$