Famous Theorems of Mathematics/Number Theory/Totient Function

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

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

The proof of the identity

\sum_{1\le k\le n \atop (k,n)=1} k = \frac{1}{2} \, \varphi(n) \, n
\quad \mbox{ where } \quad
n \ge 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


such pairs, and the constituents of each pair sum to

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


\sum_{(k, n)=1} k = \frac{1}{2} \, \varphi(n) \, n
\quad \mbox{ where } \quad
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[edit]

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

\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, }

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


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} 
\left\lfloor\frac{n+1}{k}\right\rfloor^2 - \left\lfloor\frac{n}{k}\right\rfloor^2
\; + \; \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.}

This gives the following for the sum

\sum_{k|n+1, \; k<n+1} \mu(k) 
\left( 2\frac{n+1}{k} - 1 \right) \; + \; \frac{1}{2} \; \mu(n+1) =
\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(p q) \left\lfloor \frac{n}{pq} \right\rfloor^2
\; + \; \sum_{p<q<r} \mu(p q r) \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[edit]

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 \le x we have the upper bound

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

and the lower bound

\frac{1}{2 n^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}{2 n^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}{2 n^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)


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

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 \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)} + \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[edit]

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.


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 nk 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).


\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 rk achieves values arbitrarily close to zero.

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

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

Note that

 \varphi(n) \sigma(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} =
\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) \ge
\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\ge 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[edit]