# Famous Theorems of Mathematics/Number Theory/Totient Function

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

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

The proof of the identity

${\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 2}$

uses the fact that

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

because if ${\displaystyle d|n}$ and ${\displaystyle d|k}$ then ${\displaystyle d|n-k}$ and if ${\displaystyle d|n}$ and ${\displaystyle d|(n-k)}$ then ${\displaystyle d|n-(n-k)=k.}$

This means that for ${\displaystyle n>2}$ we may group the k that are relatively prime to n into pairs

${\displaystyle (k,n-k)\quad {\mbox{ where }}\quad k.

The case ${\displaystyle k=n/2}$ does not occur because ${\displaystyle n/2}$ is not an integer when n is odd, and when n is even, we have ${\displaystyle (n/2,n)=n/2>1}$ because we assumed that ${\displaystyle n>2.}$ There are

${\displaystyle {\frac {\varphi (n)}{2}}}$

such pairs, and the constituents of each pair sum to

${\displaystyle k\;+\;n-k\;=n,}$

hence

${\displaystyle \sum _{(k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 3.}$

The case ${\displaystyle 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

${\displaystyle \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 ${\displaystyle n}$. The base case is ${\displaystyle n=1}$ and we see that the claim holds:

${\displaystyle \varphi (1)/1=1={\frac {\mu (1)}{1}}\left\lfloor 1\right\rfloor .}$

For the induction step we need to prove that

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

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

${\displaystyle \sum _{k|n+1,\;k

Now the fact that

${\displaystyle \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 ${\displaystyle p_{1}^{v_{1}}p_{2}^{v_{2}}\ldots p_{q}^{v_{q}}}$ be the prime factorization of n+1. Then

${\displaystyle {\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 ${\displaystyle \mu (k).}$ This concludes the proof.

An alternate proof proceeds by substituting ${\displaystyle {\frac {\varphi (k)}{k}}=\sum _{d|k}{\frac {\mu (d)}{d}}}$ directly into the left side of the identity, giving ${\displaystyle \sum _{k=1}^{n}\sum _{d|k}{\frac {\mu (d)}{d}}.}$

Now we ask how often the term ${\displaystyle {\begin{matrix}{\frac {\mu (d)}{d}}\end{matrix}}}$ occurs in the double sum. The answer is that it occurs for every multiple ${\displaystyle k}$ of ${\displaystyle d}$, but there are precisely ${\displaystyle {\begin{matrix}\left\lfloor {\frac {n}{d}}\right\rfloor \end{matrix}}}$ such multiples, which means that the sum is

${\displaystyle \sum _{d=1}^{n}{\frac {\mu (d)}{d}}\left\lfloor {\frac {n}{d}}\right\rfloor }$

as claimed.

The trick where zero values of ${\displaystyle {\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

${\displaystyle \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 ${\displaystyle n=1}$ and we have

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

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

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

${\displaystyle {\frac {1}{2}}\sum _{k|n+1,\;k

Treating the two inner terms separately, we get

${\displaystyle (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 ${\displaystyle \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 ${\displaystyle n+1}$ as above, we have ${\displaystyle {\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

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

${\displaystyle \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:

${\displaystyle \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 ${\displaystyle {\begin{matrix}-\mu (pqr\cdots )\end{matrix}}}$, hence the number of points with relatively prime coordinates is

${\displaystyle \mu (1)\,n^{2}\;+\;\sum _{p}\mu (p)\left\lfloor {\frac {n}{p}}\right\rfloor ^{2}\;+\;\sum _{p

but this is precisely ${\displaystyle \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:

${\displaystyle {\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)}$

Using ${\displaystyle x-1<\lfloor x\rfloor \leq x}$ we have the upper bound

${\displaystyle {\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k){\frac {n^{2}}{k^{2}}}\right)={\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}}$

and the lower bound

${\displaystyle {\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k)\left({\frac {n^{2}}{k^{2}}}-2{\frac {n}{k}}+1\right)\right)}$

which is

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

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

${\displaystyle {\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)>-{\frac {1}{2n}}.}$

Now we check the order of the terms in the upper and lower bound. The term ${\displaystyle {\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}}$ is ${\displaystyle {\mathcal {O}}(1)}$ by comparison with ${\displaystyle \zeta (2)}$, where ${\displaystyle \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

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

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

${\displaystyle {\frac {1}{\zeta (s)}}=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}.}$

This means that

${\displaystyle {\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 ${\displaystyle {\begin{matrix}\int _{n+1}^{\infty }{\frac {1}{t^{2}}}dt\end{matrix}}}$ was used to estimate ${\displaystyle {\begin{matrix}\sum _{k>n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}.}$ But ${\displaystyle {\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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle p_{1},p_{2},...,p_{k}}$. Let

${\displaystyle r_{k}={\frac {\varphi (n_{k})}{n_{k}}}=\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).}$

Then

${\displaystyle {\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 ${\displaystyle H_{n}>\log n}$, we have

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

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

Note that

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

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

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

${\displaystyle \prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right)\geq \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

${\displaystyle \prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}}$

so that

${\displaystyle \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.