Proofs of totient identities

From Wikipedia, the free encyclopedia

This mathematics article is devoted entirely to providing mathematical proofs and support for claims and statements made in the article totient function. This article is currently an experimental vehicle to see how well we can provide proofs and details for a math article without cluttering up the main article itself. See Wikipedia:WikiProject Mathematics/Proofs for some current discussion. This article is "experimental" in the sense that it is a test of one way we may be able to incorporate more detailed proofs in Wikipedia.

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

1 Sum of integers relatively prime to and less than or equal to n
2 Proofs of totient identities involving the floor function
3 Average order of the totient
- 3.1 Average order of phi(n)/n
4 Inequalities
5 External links

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

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$

and the sum extends over $1 \le k \le n$ is by induction on n. Start with $n = 2$ , which gives

$1 = \frac{1}{2} \, \varphi(2) \, 2 = 1$

and the basis for the induction is established. For the induction step, first observe that

$\sum_{(k, n)=1} k = \frac{1}{2} n (n+1) - n - \sum_{d|n \atop 1 < d < n} \sum_{(k, n)=d} k.$

Working with the last term, we obtain

$\sum_{d|n \atop 1 < d < n} \sum_{(k, n)=d} k = \sum_{d|n \atop 1 < d < n} d \sum_{(l, n/d)=1} l = \sum_{d|n \atop 1 < d < n} d \; \frac{1}{2} \varphi\left(\frac{n}{d}\right)\frac{n}{d},$

where the last equality follows by induction (the sum is over $1 < d < n$ ). Additional simplification yields

$\frac{1}{2} n \sum_{d|n \atop 1 < d < n} \varphi\left(\frac{n}{d}\right) = \frac{1}{2} n \left( -1 -\varphi(n) + \sum_{d|n} \varphi\left(\frac{n}{d}\right) \right)$

$\frac{1}{2} n \left( -1 -\varphi(n) + \sum_{d|n} \varphi(d) \right) = \frac{1}{2} n \left( n-1 -\varphi(n) \right).$

Substituting back into the original equation, we find that

$\sum_{(k, n)=1} k = \frac{1}{2} n (n+1) - n -\frac{1}{2} n \left( n-1 -\varphi(n) \right)$

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

QED.

Another, more elementary proof uses the fact that

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

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 \ge 3.$

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

[edit] 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 $μ(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] x [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| \; - \; \ldots \; \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 \; + \; \ldots$

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

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

and

$\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 $ζ(2)$ , where $ζ(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.

[edit] Average order of phi(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 \frac{\mu(k)}{k^2}.$

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

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

To see the former, let n be the product of the first k primes, call them $p 1, p 2,...$ etc. Let

$r = \frac{\varphi (n)}{n} = \prod_{l=1}^k \left( 1 - \frac{1}{p_l} \right).$

Then

$\frac{1}{r} = \prod_{l=1}^k \left( 1 - \frac{1}{p_l} \right)^{-1} > \sum_{m=1}^{p_k} \frac{1}{m} = H_{p_k},$

a harmonic number. Hence

$\frac{1}{r} > \log p_k,$

and thus r gets 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) = 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}$