Fermat's little theorem

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.)