# Famous Theorems of Mathematics/Number Theory/Totient Function

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

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.

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

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

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

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

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

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

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

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.

## 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 (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).$

Then

$\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) = 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}$

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.