5.2: A Necessary Digression - Gauss’s Theorem on Sums of Euler’s Function

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

Later in this chapter we will need a fact first proved by Gauss about Euler’s \(\phi\) function:

Theorem \(\PageIndex{1}\)

For all \(n\in\NN\), \(\displaystyle\sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \phi(d) = n\ .\)

We’ll give two proofs, which illustrate different features of this situation:

Proof 1

Fix \(n\in\NN\).

Let’s define some subsets of \(\{1,\dots,n\}\), dependent upon a choice of a positive divisor \(d\mid n\), as follows \[S_d=\left\{k\in\NN\mid 1\le k\le n\ \text{and}\ \gcd(k,n)=d\right\}\ .\] These sets are disjoint since for each \(k\in\NN\) such that \(1\le k\le n\), \(d=\gcd(k,n)\) has a specific value and \(k\) is only in that \(S_d\).

For \(k\in S_d\), \(\gcd(k,n)=d\) or, by Theorem 1.5.1, \(\gcd(k/d,n/d)=1\). Thus \(\#(S_d)\) is the number of elements \(\ell\in\NN\) in the range \(1\le\ell\le n/d\) which are relatively prime to \(n/d\), i.e., \(\#(S_d)=\phi(n/d)\).

Every \(k\in\ZZ\) in the range \(1\le k\le n\) is in exactly one of these \(S_d\), for \(d\) a positive divisor of \(n\). Therefore \[\{1,\dots,n\} = \bigcup_{\substack{d\in\NN\\s.t.\ d\mid n}} S_d\] so \[n=\#\left(\{1,\dots,n\}\right) = \#\left(\bigcup_{\substack{d\in\NN\\s.t.\ d\mid n}} S_d\right) = \sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \#\left(S_d\right) = \sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \phi(n/d)\ .\] But as \(d\) runs over the positive divisors of \(n\), so does \(n/d\); in other words \[\left\{d\mid d\in\NN,\ 1\le d\le n\text{\ and\ }d\mid n\right\}=\left\{n/d\mid d\in\NN,\ 1\le d\le n\text{\ and\ }d\mid n\right\}\]

We can therefore rewrite the last big equation as \[n=\sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \phi(n/d)=\sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \phi(d)\] which is what we were trying to prove.

Proof 2

This approach will concentrate on the function \[F(n)=\sum_{\substack{d\in\NN\\s.t.\ d\mid n}} \phi(d)\ ,\] which has some very nice properties.

For example, suppose \(p\) is a prime and \(k\in\NN\). Then the divisors of \(p^k\) are \(1,p,p^2,\dots,p^k\), so \[F(p^k)=\phi(1)+\phi(p)+\phi(p^2)+\dots+\phi(p^k) =1+(p-1)+(p^2-p)+\dots+(p^k-p^{k-1}) = p^k\ .\]

Furthermore, if \(p\) and \(q\) are distinct primes, then the divisors of \(pq\) are \(1\), \(p\), \(q\), and \(pq\). Also, \(\gcd(p,q)=1\), so by Theorem 2.5.2 \[\begin{aligned} F(pq)&=\phi(1)+\phi(p)+\phi(q)+\phi(pq)\\ &=\phi(1)+\phi(p)+\phi(q)+\phi(p)\phi(q)\\ &=(1+\phi(p))(1+\phi(q))\\ &=F(p)F(q)\ ,\end{aligned}\] From this fact, one can prove (it’s an exercise below) that \(F(ab)=F(a)F(b)\) whenever \(a,b\in\NN\) are relatively prime. This means that \(F\) has the same sort of multiplicative property for relatively prime factors as does \(\phi\).

We are ready to finish the proof. So let \(n\in\NN\) be any number such that \(n>1\) (for \(n=1\), the theorem is trivial). Suppose the prime decomposition of \(n\) is given by \[n=p_1^{k_1}\cdot\cdots\cdot p_r^{k_r}\ ,\] where the primes \(\{p_1,\dots,p_r\}\) are distinct. Therefore \(\gcd(p_i^{k_i},p_j^{k_j})=1\) if \(i\neq j\) and so we can use the multiplicative property of \(F\) and our calculation of \(F\) for prime powers to conclude \[\begin{aligned} F(n)&=F(p_1^{k_1}\cdot\cdots\cdot p_r^{k_r})\\ &=F(p_1^{k_1})\cdot\cdots\cdot F(p_r^{k_r})\\ &=p_1^{k_1}\cdot\cdots\cdot p_r^{k_r}\\ &=n\ ,\end{aligned}\] which is what we wanted to prove.

Exercise \(\PageIndex{1}\)

1. Finish the second proof of Gauss’s Theorem 5.2.1 by proving that \(F(ab)=F(a)F(b)\) for all \(a,b\in\NN\) which are relatively prime.