Famous Theorems of Mathematics/Number Theory/Totient Function

This page provides proofs for identities involving the totient function and the Möbius function .

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

The proof of the identity


uses the fact that


because if   and   then   and if   and   then  

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


The case   does not occur because   is not an integer when n is odd, and when n is even, we have   because we assumed that   There are


such pairs, and the constituents of each pair sum to




The case   is verified by direct substitution and may be included in the formula.

Proofs of totient identities involving the floor function edit

The proof of the identity


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


For the induction step we need to prove that


The key observation is that


so that the sum is


Now the fact that


is a basic totient identity. To see that it holds, let   be the prime factorization of n+1. Then


by definition of   This concludes the proof.

An alternate proof proceeds by substituting   directly into the left side of the identity, giving  

Now we ask how often the term   occurs in the double sum. The answer is that it occurs for every multiple   of  , but there are precisely   such multiples, which means that the sum is


as claimed.

The trick where zero values of   are filtered out may also be used to prove the identity


The base case is   and we have


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


Next observe that


This gives the following for the sum


Treating the two inner terms separately, we get


The first of these two is precisely   as we saw earlier, and the second is zero, by a basic property of the Möbius function (using the same factorization of   as above, we have  .) This concludes the proof.

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


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   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


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


and the signs are  , hence the number of points with relatively prime coordinates is


but this is precisely   and we have the claim.

Average order of the totient edit

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


Using   we have the upper bound


and the lower bound


which is


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




Now we check the order of the terms in the upper and lower bound. The term   is   by comparison with  , where   is the Riemann zeta function. The next largest term is the logarithmic term from the lower bound.

So far we have shown that


It remains to evaluate   asymptotically, which we have seen converges. The Euler product for the Riemann zeta function is


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


This means that


where the integral   was used to estimate   But   and we have established the claim.

Average order of φ(n)/n edit

The material of the preceding section, together with the identity


also yields a proof that


Reasoning as before, we have the upper bound


and the lower bound


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

Inequalities edit

We first show that


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


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 nk be the product of the first k primes, call them  . Let




a harmonic number. Hence, by the well-known bound  , we have


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

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


Note that


which is


The upper bound follows immediately since


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


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


so that


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

External links edit