Famous Theorems of Mathematics/Number Theory/Totient Function

This page provides proofs for identities involving the totient function $\phi (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 _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}\phi (n)n\text{ where }n\ge 2$

uses the fact that

$(k,n)=d\iff (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)\text{ where }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{\phi (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}\phi (n)n\text{ where }n\ge 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{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor$

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

$\phi (1)/1=1=\frac{\mu (1)}{1}\lfloor 1\rfloor .$

For the induction step we need to prove that

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

The key observation is that

$\lfloor \frac{n+1}{k}\rfloor -\lfloor \frac{n}{k}\rfloor =\{\begin{array}{cc}1,& \text{if }k|(n+1)\\ 0,& \text{otherwise, }\end{array}$

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{\phi (n+1)}{n+1}$

is a basic totient identity. To see that it holds, let $p_1^{v_1}{p}_2^{v_2}\dots p_q^{v_q}$ be the prime factorization of n+1. Then

$\frac{\phi (n+1)}{n+1}=\prod _{l=1}^q(1-\frac{1}{p_l})=\sum _{k|n+1}\frac{\mu (k)}{k}$

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

An alternate proof proceeds by substituting $\frac{\phi (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{array}{c}\frac{\mu (d)}{d}\end{array}$ occurs in the double sum. The answer is that it occurs for every multiple $k$ of $d$, but there are precisely $\begin{array}{c}\lfloor \frac{n}{d}\rfloor \end{array}$ such multiples, which means that the sum is

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

as claimed.

---

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

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

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

$\phi (1)=1=\frac{1}{2}(1+\mu (1){\lfloor \frac{1}{1}\rfloor }^2)$

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

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

Next observe that

${\lfloor \frac{n+1}{k}\rfloor }^2-{\lfloor \frac{n}{k}\rfloor }^2=\{\begin{array}{cc}2\frac{n+1}{k}-1,& \text{if }k|(n+1)\\ 0,& \text{otherwise.}\end{array}$

This gives the following for the sum

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

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 $\phi (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{array}{c}\sum _{k|n+1}\mu (k)=\prod _{l=1}^q(1-1)=0\end{array}$.) This concludes the proof.

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

$-1+2\sum _{k=1}^n\phi (k)=\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\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}|A_p\cap A_q|+\sum _{p<q<r}|A_p\cap A_q\cap A_r|-\cdots \pm |A_p\cap \cdots \cap A_s|.$

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|={\lfloor \frac{n}{p}\rfloor }^2,|A_p\cap A_q|={\lfloor \frac{n}{pq}\rfloor }^2,|A_p\cap A_q\cap A_r|={\lfloor \frac{n}{pqr}\rfloor }^2,\dots$

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

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

but this is precisely $\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\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\phi (k)=\frac{3}{{\pi }^2}+𝒪\left(\frac{\log n}{n}\right)$

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

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

and the lower bound

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

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{array}{c}\sum _{k=1}^n\frac{\mu (k)}{k^2}\end{array}$ is $𝒪(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\phi (k)=\frac{1}{2}\sum _{k=1}^n\frac{\mu (k)}{k^2}+𝒪\left(\frac{\log n}{n}\right)$

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

$\zeta (s)=\prod _p{(1-\frac{1}{p^s})}^{-1}\text{ for }\mathrm{\Re }(s)>1.$

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

$\frac{1}{\zeta (s)}=\prod _p(1-\frac{1}{p^s})=\sum _{n\ge 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)}+𝒪\left(\frac{1}{n}\right)$

where the integral $\begin{array}{c}\underset{n+1}{\overset{\mathrm{\infty }}{\int }}\frac{1}{t^2}dt\end{array}$ was used to estimate $\begin{array}{c}\sum _{k>n}\frac{\mu (k)}{k^2}\end{array}.$ But $\begin{array}{c}\frac{1}{2}\frac{1}{\zeta (2)}=\frac{3}{{\pi }^2}\end{array}$ 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{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor$

also yields a proof that

$\frac{1}{n}\sum _{k=1}^n\frac{\phi (k)}{k}=\frac{6}{{\pi }^2}+𝒪\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{\phi (n)}{n}=0\text{ and }\lim \sup \frac{\phi (n)}{n}=1.$

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

$\frac{\phi (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{\phi (n_k)}{n_k}=\prod _{i=1}^k(1-\frac{1}{p_i}).$

Then

$\frac{1}{r_k}=\prod _{i=1}^k{(1-\frac{1}{p_i})}^{-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}<\phi (n)\sigma (n)<n^2$.

Note that

$\phi (n)\sigma (n)=n\prod _{l=1}^q(1-\frac{1}{p_l})\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(p_l^{v_l}-\frac{1}{p_l})=n^2\prod _{l=1}^q(1-\frac{1}{p_l^{v_l+1}}).$

The upper bound follows immediately since

$\prod _{l=1}^q(1-\frac{1}{p_l^{v_l+1}})<1.$

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

$\prod _{l=1}^q(1-\frac{1}{p_l^{v_l+1}})\ge \prod _{l=1}^q(1-\frac{1}{p_l^2})>\prod _p(1-\frac{1}{p^2}),$

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

$\prod _p(1-\frac{1}{p^s})=\sum _{n\ge 1}\frac{\mu (n)}{n^s}=\frac{1}{\zeta (s)}$

so that

$\prod _p(1-\frac{1}{p^2})=\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]$