Toolkit 52: Euler's Theorem — MathGoldMedalist

Let

r_1,r_2,\ldots,r_{\varphi(n)}

be all the integers from 1 to $n$ that are relatively prime to $n$ .

Since

\gcd(a,n)=1

the numbers

ar_1,ar_2,\ldots,ar_{\varphi(n)}

are also relatively prime to $n$ .

Moreover, no two of them are congruent modulo $n$ . Indeed, if

ar_i\equiv ar_j\pmod n

then, since $\gcd(a,n)=1$ , we can cancel $a$ , giving

r_i\equiv r_j\pmod n

Therefore,

ar_1,ar_2,\ldots,ar_{\varphi(n)}

are just a rearrangement modulo $n$ of

r_1,r_2,\ldots,r_{\varphi(n)}

Hence

(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n

Thus

a^{\varphi(n)}r_1r_2\cdots r_{\varphi(n)} \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n

Since every $r_i$ is relatively prime to $n$ , we can cancel

r_1r_2\cdots r_{\varphi(n)}

Therefore,

\boxed{a^{\varphi(n)}\equiv1\pmod n}