TAOCP 1.2.4 Exercise 28
Let $R={r_1,r_2,\ldots,r_{\varphi(m)}}$ be the set of integers in ${0,1,\ldots,m-1}$ that are relatively prime to $m$.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 28. ▶ [M25] Show that the method used to prove Theorem F can be used to prove the following extension, called Euler’s theorem: $a^{\varphi(m)} \equiv 1$ (modulo $m$), for any positive integer $m$, when $a \perp m$. (In particular, the number $n'$ in exercise 19 may be taken to be $n^{\varphi(m)-1} \bmod m$.)
Verified: yes
Solve time: 39s
Solution
Let $R={r_1,r_2,\ldots,r_{\varphi(m)}}$ be the set of integers in ${0,1,\ldots,m-1}$ that are relatively prime to $m$. By definition, $|R|=\varphi(m)$.
Assume that $a \perp m$. Consider the numbers
$$ ar_1 \bmod m,\qquad ar_2 \bmod m,\qquad \ldots,\qquad ar_{\varphi(m)} \bmod m. $$
First, each of these numbers is relatively prime to $m$. Since $a \perp m$ and $r_i \perp m$, any common divisor of $ar_i$ and $m$ would divide both $a$ and $m$ or both $r_i$ and $m$; hence $ar_i \perp m$. Therefore each residue $ar_i \bmod m$ belongs to $R$.
Second, these residues are distinct. Suppose
$$ ar_i \bmod m = ar_j \bmod m. $$
By the definition of congruence (5),
$$ ar_i \equiv ar_j \pmod m. $$
Since $a \perp m$, Law B applies, yielding
$$ r_i \equiv r_j \pmod m. $$
But $r_i$ and $r_j$ are integers in ${0,1,\ldots,m-1}$, so congruence modulo $m$ implies equality:
$$ r_i=r_j. $$
Hence the numbers
$$ ar_1 \bmod m,\qquad ar_2 \bmod m,\qquad \ldots,\qquad ar_{\varphi(m)} \bmod m $$
are exactly the elements of $R$, in some order.
By Law A, the product of these congruent sets satisfies
$$ (ar_1)(ar_2)\cdots(ar_{\varphi(m)}) \equiv r_1r_2\cdots r_{\varphi(m)} \pmod m. $$
Factoring out $a^{\varphi(m)}$ gives
$$ a^{\varphi(m)}(r_1r_2\cdots r_{\varphi(m)}) \equiv r_1r_2\cdots r_{\varphi(m)} \pmod m. $$
Each factor $r_i$ is relatively prime to $m$, so repeated application of Law B permits cancellation of all factors $r_1,r_2,\ldots,r_{\varphi(m)}$. Therefore
$$ a^{\varphi(m)} \equiv 1 \pmod m. $$
This proves Euler's theorem.
For the parenthetical statement, exercise 19 requires a number $n'$ such that
$$ nn' \equiv 1 \pmod m, $$
when $n \perp m$. By Euler's theorem,
$$ n^{\varphi(m)} \equiv 1 \pmod m. $$
Hence
$$ n\cdot n^{\varphi(m)-1}\equiv 1 \pmod m. $$
Therefore
$$ n' = n^{\varphi(m)-1}\bmod m $$
is a valid choice.
This completes the proof.
∎