Theorem 02   If $a, p \in \mathbb{Z}$ with $p$ a prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod{p}$ .

Proof. We will make use of Lagrange's Theorem: Let $G$ be a finite group and let $H$ be a subgroup of $G$ . Then the order of $H$ divides the order of $G$ .

Let $G=(\Ints/p\Ints)^\times$ and let $H$ be the multiplicative subgroup of $G$ generated by $a$ (so $H=\{ 1, a ,a^2,\ldots \}$ ). Notice that the order of $H$ , $h=|H|$ is also the order of $a$ , i.e. the smallest natural number $n>1$ such that $a^n$ is the identity in $G$ , i.e. $a^h\equiv 1 \mod p$ .

By Lagrange's theorem $h \mid |G|=p-1$ , so $p-1=h\cdot m$ for some $m$ . Thus: $$a^{p-1}=(a^h)^m\equiv 1^m \equiv 1 \mod p$$ as claimed.