Proof. Consider the $p-1$ integers $a, 2 a, \ldots,(p-1) a$. None of these integers are divisible by $p$, for if $p \mid j a$, then by Lemma $2.3, p \mid j$, since $p \mid a$. This is impossible because $1 \leqslant j \leqslant p-1$. Furthermore, no two of the integers $a, 2 a, \ldots,(p-1) a$ are congruent modulo $p$. To see this, assume that $j a \equiv k a(\bmod p) . \quad$ Then, from Corollary 3.1 , since $(a, p)=1$, we have $j \equiv k(\bmod p)$. This is impossible, since $j$ and $k$ are positive integers less than $p-1$.

Since the integers $a, 2 a, \ldots,(p-1) a$ are a set of $p-1$ integers all incongruent to zero, and no two congruent modulo $p$, we know that the least positive residues of $a, 2 a, \ldots,(p-1) a$, taken in some order, must be the integers $1,2, \ldots, p-1$. As a consequence, the product of the integers $a, 2 a, \ldots,(p-1) a$ is congruent modulo $p$ to the product of the first $p-1$ positive integers. Hence,
$$a \cdot 2 a \cdots(p-1) a \equiv 1 \cdot 2 \cdots(p-1)(\bmod p)$$

Therefore,
$$a^{p-1}(p-1)!\equiv(p-1)!(\bmod p)$$

Since $((p-1)!, p)=1$, using Corollary 3.1 , we cancel $(p-1)$ ! to obtain
$$a^{p-1} \equiv 1(\bmod p)$$