Pequeño teorema de Fermat

Consideremos los números $a, 2a, 3a, \dots , (p-1)a$. Cada uno de éstos número tiene distinto residuo al dividir entre $p$. Ya que, si $ia \equiv ja \pmod{p}$ y como $p$ y $a$ son primos relaivos (pues $p$ no divide a $a$) se tendrá que $i \equiv j \pmod{p}$.

Ahora, como $i$ e $j$ son residuos de $p$ y son congruentes, deberá de ser que $i = j$.

Como todos los números $a, 2a, 3a, \dots , (p-1)a$ tienen distinto residuo y ninguo de ellos tiene residuo cero, entonces, cada uno de esos número será congruente con uno y sólo uno de los residuos $1, 2, 3, \dots, {p-1}$.

Por ello, se puede escribir la congruencia:

$$a \cdot 2a \cdot 3a \cdots (p-1) \equiv 1\cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$$

entonces,

$$[(p-1)!]a^{p-1} \equiv (p-1)! \pmod{p}$$

Como $(p-1)!$ es primos relativo con $p$ se puede cancelar $(p-1)!$ en ambos lados de la congruencia. Y como consecuencia se tendrá que:

$$a^{p-1} \equiv 1 \pmod{p}$$