# Famous Theorems of Mathematics/Number Theory/Totient Function

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\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
    $(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
    ${\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\geq 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<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
    $\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] × [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 (pq)\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2}\;+\;\sum _{p<q<r}\mu (pqr)\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

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 \leq x$ we have the upper bound
    ${\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
    ${\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
    ${\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
    $-{\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}{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 ${\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\geq 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 n$_k$ 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 r$_k$ achieves values arbitrarily close to zero.
We use the same factorization of n as in the first section to prove that
    ${\frac {6n^{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)\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
    $\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 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

* Chris K. Caldwell, What is the probability that gcd(n,m)=1?
* Bordellès, Olivier, Numbers prime to q in $[1,n]$