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}$

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}$$