Proofs involving the totient function

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

um of integers relatively prime to and less than or equal to "n"

Claim::$sum\_\{1le\; kle\; n\; atop\; \{gcd(k,n)=1\; k\; =\; frac\{1\}\{2\}\; ,\; varphi(n)\; ,\; nquad\; ext\{\; for\; integers\; \}n\; ge\; 2.$Since $gcd(n,n)\; e\; 1$and $gcd(k,n)=gcd(n-k,n)$ for all integers $k$, a change of index yields:$sum\_\{1le\; kle\; n\; atop\; \{gcd(k,n)=1\; k\; ,=\; sum\_\{1le\; kle\; n\; atop\; \{gcd(k,n)=1\; (n-k)$.Therefore:$2sum\_\{1le\; kle\; n\; atop\; \{gcd(k,n)=1\; k\; ,=sum\_\{1le\; kle\; n\; atop\; \{gcd(k,n)=1\; (k+n-k)\; =\; varphi(n),n$.

Proofs of totient identities involving the floor function

The proof of the identity

:$sum\_\{k=1\}^nfrac\{varphi(k)\}\{k\}\; =\; sum\_\{k=1\}^nfrac\{mu(k)\}\{k\}leftlfloorfrac\{n\}\{k\}\; ight\; floor$

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\}\; leftlfloor\; 1\; ight\; floor.$

For the induction step we need to prove that

:$frac\{varphi(n+1)\}\{n+1\}\; =$

sum_{k=1}^nfrac{mu(k)}{k}left(leftlfloorfrac{n+1}{k} ight floor - leftlfloorfrac{n}{k} ight floor ight)+ frac{mu(n+1)}{n+1}.

The key observation is that

:

so that the sum is:

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\}\; ight)=\; sum\_\{k|n+1\}\; frac\{mu(k)\}\{k\}$

by definition of $mu(k).$ This concludes the proof.cn|date=December 2007

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 occurs in the double sum. The answer is that it occurs for every multiple $k$ of $d$, but there are precisely such multiples, which means that the sum is

:$sum\_\{d=1\}^nfrac\{mu(d)\}\{d\}leftlfloorfrac\{n\}\{d\}\; ight\; floor$

as claimed.cn|date=December 2007

----

The trick where zero values ofcn|date=December 2007 are filtered out may also be used to prove the identity

:$sum\_\{k=1\}^nvarphi(k)\; =\; frac\{1\}\{2\}left(1+\; sum\_\{k=1\}^n\; mu(k)leftlfloorfrac\{n\}\{k\}\; ight\; floor^2\; ight).$

The base case is $n=1$ and we have

:$varphi(1)\; =\; 1\; =\; frac\{1\}\{2\}\; left(1+\; mu(1)\; leftlfloorfrac\{1\}\{1\}\; ight\; floor^2\; ight)$

and it holds. The induction step requires us to show that

:$varphi(n+1)\; =\; frac\{1\}\{2\}\; sum\_\{k=1\}^n\; mu(k)left(leftlfloorfrac\{n+1\}\{k\}\; ight\; floor^2\; -\; leftlfloorfrac\{n\}\{k\}\; ight\; floor^2\; ight);\; +\; ;\; frac\{1\}\{2\}\; ;\; mu(n+1)\; ;\; leftlfloorfrac\{n+1\}\{n+1\}\; ight\; floor^2.$

Next observe thatcn|date=December 2007

:

This gives the following for the sum:

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 .) This concludes the proof.

This result may also be proved by inclusion-exclusion. Rewrite the identity as:$-1\; +\; 2sum\_\{k=1\}^nvarphi(k)\; =\; sum\_\{k=1\}^n\; mu(k)leftlfloorfrac\{n\}\{k\}\; ight\; floor^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

:

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\; ight|\; =\; leftlfloor\; frac\{n\}\{p\}\; ight\; floor^2,\; ;left|\; A\_p\; cap\; A\_q\; ight|\; =\; leftlfloor\; frac\{n\}\{pq\}\; ight\; floor^2,\; ;left|\; A\_p\; cap\; A\_q\; cap\; A\_r\; ight|\; =\; leftlfloor\; frac\{n\}\{pqr\}\; ight\; floor^2,\; ;\; ldots$

and the signs are , hence the number of points with relatively prime coordinates is

but this is precisely $sum\_\{k=1\}^n\; mu(k)\; leftlfloor\; frac\{n\}\{k\}\; ight\; floor^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\}\; ight)$

Using we have the upper bound:$frac\{1\}\{2\; n^2\}\; left(1+\; sum\_\{k=1\}^n\; mu(k)frac\{n^2\}\{k^2\}\; ight)\; =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\}\; -\; 2frac\{n\}\{k\}\; +\; 1\; ight)\; ight)$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 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\}\; ight)$

It remains to evaluate 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\}\; ight)^\{-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\}\; ight)=\; 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\}\; ight)$where the integralwas used to estimateBut and we have established the claim.

Average order of φ("n")/"n"

The material of the preceding section, together with the identity

:$sum\_\{k=1\}^nfrac\{varphi(k)\}\{k\}\; =\; sum\_\{k=1\}^nfrac\{mu(k)\}\{k\}leftlfloorfrac\{n\}\{k\}\; ight\; floor$

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\}\; ight).$

Reasoning as before, we have the upper bound:$frac\{1\}\{n\}\; sum\_\{k=1\}^nfrac\{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\}^nfrac\{mu(k)\}\{k\}\; +sum\_\{k=1\}^n\; 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\}\; ight).$

Then

:$frac\{1\}\{r\_k\}\; =\; prod\_\{i=1\}^k\; left(\; 1\; -\; frac\{1\}\{p\_i\}\; ight)^\{-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

:.

Note that

:$varphi(n)\; sigma(n)\; =\; n\; prod\_\{l=1\}^q\; left(1\; -\; frac\{1\}\{p\_l\}\; ight)\; prod\_\{l=1\}^q\; frac\{p\_l^\{v\_l+1\}-1\}\{p\_l-1\}\; =nprod\_\{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\}\; ight)\; =n^2\; prod\_\{l=1\}^q\; left(1\; -\; frac\{1\}\{p\_l^\{v\_l+1\; ight).$

The upper bound follows immediately since

:

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\; ight)\; geprod\_\{l=1\}^q\; left(1\; -\; frac\{1\}\{p\_l^2\}\; ight)\; >prod\_p\; left(1\; -\; frac\{1\}\{p^2\}\; ight),$

where the product is over all primes. We have already seen this product, as in

:$prod\_p\; left(1\; -\; frac\{1\}\{p^s\}\; ight)\; =sum\_\{nge\; 1\}\; frac\{mu(n)\}\{n^s\}\; =\; frac\{1\}\{zeta(s)\}$

so that

:$prod\_p\; left(1\; -\; frac\{1\}\{p^2\}\; ight)\; =\; 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, " [http://primes.utm.edu/notes/relprime.html What is the probability that gcd(n,m)=1?] "