Fermat's little theorem and Euler's theorem

The nonzero residues modulo a prime $p$ form a closed system under multiplication: multiplying every one of them by a fixed $a$ just shuffles them among themselves. Repeating this shuffle $p-1$ times must therefore return every element to its own position, which is exactly the statement $a^{p-1}\equiv1\pmod p$.

Consider the set $S=\{1,2,\dots,p-1\}$ of nonzero residues modulo $p$, and the map $x \mapsto ax \bmod p$ sending each element of $S$ to a residue.

This map is injective on $S$: if $ax\equiv ay\pmod p$ for $x,y\in S$, then since $\gcd(a,p)=1$, the cancellation law (proved in the previous topic) gives $x\equiv y\pmod p$, hence $x=y$ because both lie in $\{1,\dots,p-1\}$. Also no $ax$ can be $\equiv 0\pmod p$ for $x\in S$, since $p$ is prime and divides neither $a$ nor $x$. So the map actually lands back inside $S$.

An injective map from the finite set $S$ to itself is automatically a bijection. Therefore $\{a\cdot1,a\cdot2,\dots,a\cdot(p-1)\} \pmod p$ is simply $\{1,2,\dots,p-1\}$ written in a different order.

Multiply all $p-1$ elements of both sets together. On one side we get $(a\cdot1)(a\cdot2)\cdots(a\cdot(p-1)) = a^{p-1}\,(p-1)!$; on the other, since it's the same numbers reordered, we get exactly $(p-1)!$. So $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$.

Since $p$ is prime, none of $1,2,\dots,p-1$ is divisible by $p$, so $\gcd((p-1)!,p)=1$. Applying the cancellation law once more to remove the common factor $(p-1)!$ from both sides gives $a^{p-1}\equiv1\pmod p$. $\blacksquare$

(Group-theoretic restatement: the nonzero residues form a group of order $p-1$ under multiplication since $p$ is prime, and Lagrange's theorem says the order of any element — here, the smallest $k$ with $a^k\equiv1$ — must divide the group's order $p-1$; hence $a^{p-1}\equiv1\pmod p$ automatically.)

This is exactly Fermat's argument with a general modulus $n$: instead of all nonzero residues (which only form a closed multiplicative system when $n$ is prime), we restrict to the residues actually coprime to $n$ — the ones that have inverses — and the same shuffling argument applies to that smaller, closed set of size $\varphi(n)$.

Let $R=\{r_1,\dots,r_{\varphi(n)}\}$ be a reduced residue system modulo $n$: representatives of every residue class coprime to $n$.

Multiplication by $a$ permutes $R$: for each $r_i$, $\gcd(ar_i,n)=1$ because $\gcd(a,n)=1$ and $\gcd(r_i,n)=1$ (a product is coprime to $n$ iff both factors are), so $ar_i \bmod n$ is again a member of the coprime residue classes; and the map $r_i\mapsto ar_i \bmod n$ is injective by the cancellation law, since $\gcd(a,n)=1$.

An injective map from the finite set $R$ to itself (up to residue) is a bijection, so $\{ar_1,\dots,ar_{\varphi(n)}\} \pmod n$ is just $\{r_1,\dots,r_{\varphi(n)}\}$ reordered.

Multiplying all $\varphi(n)$ elements of each set: $a^{\varphi(n)}\, (r_1 r_2\cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$. Since each $r_i$ is coprime to $n$, so is their product $R=\prod r_i$, i.e. $\gcd(R,n)=1$.

Cancel $R$ from both sides (valid since $\gcd(R,n)=1$) to get $a^{\varphi(n)}\equiv1\pmod n$. $\blacksquare$

This is again Lagrange's theorem in disguise: the residues coprime to $n$ form a group of order $\varphi(n)$ under multiplication (the group of units $(\mathbb{Z}/n\mathbb{Z})^{*}$), and the order of any element divides $\varphi(n)$.