| | |
There is a natural question to ask upon discovering Fermat's Little Theorem -- which recall, assures us that if $p$ is prime and $a$ is a positive integer relatively prime to $p$, then $a^{p-1} \equiv 1 \pmod{p}$
So we again look at the behavior of powers $a^1, a^2, a^3, \ldots \pmod{n}$ but this time focus on when $n$ is composite...
We note that for a given modulus $n$, for any value of $a \neq 1$ which is not relatively prime $n$, it must be true that $a^n \not \equiv 1 \pmod{n}$, as otherwise $a$ would have a multiplicative inverse of $a^{n-1}$ (and this would contradict the known result that numbers not relatively prime to the modulus can't have multiplicative inverses).
However, if we focus on the values of $a$ that are relatively prime to $n$, we again notice a peculiar vertical line of ones, as can be seen here when looking at powers $\pmod{14}$
$$\begin{array}{c||c|c|c|c|c|c|c} a & a^2 & a^3 & a^4 & a^5 & a^6 & a^7 & a^8\\\hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\\hline 3 & 9 & 13 & 11 & 5 & 1 & 3 & 9\\\hline 5 & 11 & 13 & 9 & 3 & 1 & 5 & 11\\\hline 9 & 11 & 1 & 9 & 11 & 1 & 9 & 11\\\hline 11 & 9 & 1 & 11 & 9 & 1 & 11 & 9\\\hline 13 & 1 & 13 & 1 & 13 & 1 & 13 & 1\\\hline \end{array}$$In the above example, when the modulus is $14$, we see a vertical line of ones when $a$ has an exponent of $6$. With a little experimentation using different moduli, we discover that for any positive integer modulus $n$, an exponent that always produces a vertical line of $1$'s is the number of positive integers less than $n$ and relatively prime to $n$ -- a number we typically denote by $\varphi(n)$.
Euler observed this too, and the result is normally attributed to him:
| Euler's Theorem If $n$ is a positive integer and $a$ is an integer with $gcd(a,n)=1$, then $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ |
The proof of Euler's Theorem directly parallels that of Fermat's Little Theorem, except that we don't consider the set of products $a \cdot 1, a \cdot 2, a \cdot 3, \ldots, a \cdot (p-1)$, but instead, we start with the set of products given by
$$a \cdot r_1, a \cdot r_2, a \cdot r_3, \ldots, a \cdot r_{\varphi(n)}$$where $r_1, r_2, r_3, \ldots, r_{\varphi(n)}$ are the positive integers less than $n$ that are relatively prime to $n$.
With a little effort, we can show that these products -- when reduced $\pmod{n}$ -- are all distinct, non-zero, and relatively prime to $n$. (Can you figure out how?)
Assuming we can make such arguments, it must then be the case that these reduced values agree with the values of $r_1, r_2, r_3, r_4, \ldots, r_{\varphi(n)}$, except that they might possibly be in a different order.
This allows us to conclude
$$(a r_1)(a r_2)(a r_3) \ldots, (a r_{\varphi(n)}) \equiv r_1 r_2 r_3 r_4 \ldots, r_{\varphi(n)} \pmod{n}$$Collecting the $a$'s together yields
$$a^{\varphi(n)} \cdot r_1 r_2 r_3 \cdots r_{\varphi(n)} \equiv r_1 r_2 r_3 \ldots, r_{\varphi(n)} \pmod{n}$$Finally, multiplying both sides by the multiplicative inverse of each $r_i$ (which we are guaranteed must exist, since each $r_i$ is relatively prime to $n$), we have the desired result,
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$