Fermat's Little Theorem: If $p$ is prime and does not divide $a$, then $a^{p-1} \equiv 1 (\mbox{mod } p)$.

Proof: List the multiples of $a$ up to $a(p-1)$:

$$ a, a2, a3, \dots , a(p-1).$$

For any $r$ and $s$ with, $ra \equiv sa (\mbox{mod } p)$, we have $r \equiv s (\mbox{mod } p)$, so that the list above contains $p-1$ many distinct numbers.

Thus, the list above is some ordering of the list $1, 2, 3, \dots p-1$ modulo $p$. This gives us $$ a\cdot a2 \cdot a3 \cdot \cdots a(p-1) \equiv (p-1)! (\mbox{mod } p) $$

Finally we see

$$ a^{p-1} \equiv 1 (\mbox{mod } p). $$