The phi function is a useful tool, but it is also interesting in its own right. Problem 5 in section 3.8 suggested an intriguing identity; it's true in general, and we'll prove it.

Suppose $n>1$. If $d$ is a positive divisor of $n$, then there is a positive integer $e$ such that $n=de$. Observe that as $d$ varies over all the positive divisors of $n$, so does $e$.

Example 3.9.1 If $n=12$, then as $d$ runs through the list $1$, $2$, $3$, $4$, $6$, $12$, $e$ takes on the values $12$, $6$, $4$, $3$, $2$, $1$, respectively. $\square$

Suppose that $n=de$. Let $ G_e = \{x: 0\le x< n \hbox{ and } (x,n)=e\}$, that is, $G_e$ consists of all numbers whose gcd with $n$ is $e$. Every $x\in \{0,1,…, n-1\}$ is contained in $G_e$ for exactly one divisor $e$ of $n$, because $(x,n)$ is a divisor of $n$. In other words, the collection of all the sets $G_e$ as $e$ runs through the divisors of $n$ partitions the set $\{0,1,…, n-1\}$.

Example 3.9.2 If $n=12$, then $$\eqalign{ G_1&=\{1,5,7,11\},\quad G_2=\{2,10\},\quad G_3=\{3,9\},\cr G_4&=\{4,8\},\quad G_6=\{6\},\quad G_{12}=\{0\}.\cr}$$ If $n=15$, then $$\eqalign{ G_1&=\{1,2,4,7,8,11,13,14\},\quad G_3=\{3,6,9,12\},\cr G_5&=\{5,10\},\quad G_{15}=\{0\}.\cr} $$ $\square$

Notice that each $G_e$ consists of some multiples of $e$. This is hardly a surprise, since it follows immediately from the definition of $G_e$. Nevertheless, this simple fact can be exploited in a surprising way. Form a new collection of sets by factoring $e$ out of the elements of $G_e$. For the example above, this gives the following two lists of sets: $$ \{1,5,7,11\},\quad \{1,5\},\quad \{1,3\}, \quad \{1,2\},\quad \{1\},\quad \{0\},$$ and $$ \{1,2,4,7,8,11,13,14\},\quad \{1,2,3,4\},\quad \{1,2\},\quad \{0\}. $$ Now, it's not immediately obvious, but with the exception of $\{0\}$, every one of these sets is "almost'' a $\U_d$ (what's missing is the $[\;]$ around each element): $\U_{12}$, $\U_6$, $\U_4$, $\U_3$, $\U_2$, $\U_{15}$, $\U_5$, and $\U_3$, respectively. Moreover, notice that the subscript $d$ in every case is $n/e$. This leads us to define $$ R_d=\{y:0\le y< d{\quad\rm and\quad }(y,d)=1\}. $$ Notice that this definition makes sense even for $d=1$, namely, $R_1=\{0\}$, and in every case, the number of elements in $R_d$ is $\phi(d)$ (because $R_d$ is almost $\U_d$—missing the $[\;]$ again). Based on these examples, it's natural to speculate that multiplication by $e$ sets up a one-to-one correspondence between $R_d$ and $G_e$ (assuming that $n=de$).

Lemma 3.9.3 If $n=de$, then $G_e$ and $R_d$ have the same number of elements. In fact, a 1-1 correspondence between the two sets is obtained by multiplying every element of $R_d$ by $e$. As a result, there are $\phi (d)$ elements in $G_e$.

Proof. Note that $$ 0\le y< d \quad\hbox{iff}\quad 0\le ey< ed \quad\hbox{iff}\quad 0\le ey< n, $$ and $$ (y,d)=1\quad\hbox{iff}\quad (ey,ed)=e\quad\hbox{iff}\quad (ey,n)=e. $$ (See exercise 4 of section 3.6.) Together these facts imply that $y\in R_d$ if and only if $ey\in G_e$.$\qed$

Now we can prove the theorem suggested by problem 5 in section 3.8.

Theorem 3.9.4 Suppose $n$ is a positive integer. Then $$ n=\sum_{0< d\vert n} \phi(d). $$

Proof. Since each of the $n$ numbers from $0$ to $n-1$ is in exactly one $G_e$, $$ n=\sum_{0< e\vert n}|G_e|=\sum_{0< e\vert n}\phi(d)= \sum_{0< d\vert n}\phi(d). $$ The last equality is valid because as $e$ ranges over the positive divisors of $n$, so does $d$, that is, the two sums are exactly the same, but they add up the terms in opposite orders.$\qed$

Example 3.9.5 If $n=20$, $$ \phi(1)+\phi(2)+\phi(4)+\phi(5)+\phi(10)+\phi(20)=1+1+2+4+4+8=20. $$ If $n=33$, $$ \phi(1)+\phi(3)+\phi(11)+\phi(33)=1+2+10+20=33. $$ $\square$

Exercises 3.9

Ex 3.9.1 For each given $n$, find the sets $R_d$, $G_e$ and verify Theorem 3.9.4.

Ex 3.9.2 Give a direct proof of Theorem 3.9.4 for the case that $n=p^a$ ($p$ prime); use Theorem 3.8.4.

Ex 3.9.3 Give a direct proof of Theorem 3.9.4 for the case $n=pq$, where $p$ and $q$ are distinct primes.

Ex 3.9.4 Show that if $n$ is positive and $(a,n)=g$, then $\exists x(ax\equiv b \pmod n)$ iff $g|b$.

Suppose we try to find all solutions to $$ ax\equiv b\pmod n. $$ Let $g=(a,n)$. If $g\notdiv b$, then there are no solutions, by the last problem. Otherwise, $a=rg$, $b=sg$, and $n=n'g$. So by exercise 8 of section 3.1, $$ rx\equiv s \pmod {{n'}}. $$ By exercise 4 of section 3.4, $r$ and $n'$ are relatively prime. So by Theorem 3.4.2 there is a $t$ such that $tr\equiv 1 \pmod {n'}$, and $$ x\equiv trx\equiv ts \pmod {{n'}}. $$ So if $x$ is a solution to $ax\equiv b\pmod n$, then $x\equiv ts\pmod{n'}$. In fact, every such $x$ really is a solution: Suppose $x=n'q+ts$ for some $q$. Then $$\eqalign{ ax=an'q+ats&=rgn'q+rgts\cr &=rnq+gs(n'k+1)\cr &=rnq+gn'ks+gs\cr &=rnq+nks+b,\cr} $$ so $ax\equiv b\pmod{n}$.

Example: $12x\equiv 10 \pmod {28}$ has no solutions since $(12,28)=4\notdiv 10$. However, if we consider a slightly different problem, $$ 12x\equiv 8 \pmod {28},$$ we can reduce it to $$ 3x\equiv 2\pmod 7. $$ Note that $3\cdot 5\equiv 1\pmod 7$, so the answer is $$ x\equiv 10 \equiv 3\pmod 7, $$ i.e., $x\in\{…, -11,-4,3,10,…\}$.

Ex 3.9.5 Solve the following congruences:

Ex 3.9.6 Suppose $n=p_1^{e_1}\cdots p_i^{e_i}$, where $e_1$,…, $e_i$ are positive; $m=p_1\cdots p_i$; and $[x]\in \Z_n$. Show that there is a positive integer $k$ such that $[x]^k=[0]$ iff $m\vert x$.

The subset of $\Z_n$ consisting of elements $[x]$ such that $[x]^k=[0]$ for some $k$, is called the radical of $\Z_n$.

Ex 3.9.7 If $[x]$ is in the radical of $\Z_n$, show that $[1-x]\in \U_n$.