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.