Famous Theorems of Mathematics/Number Theory/Totient Function

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]