Demostración del Pequeño Teorema de Fermat

El pequeño teorema de Fermat establece que:

Sea $p$ un número primo y $a$ un número natural coprimo con $p$.

$a^{p-1}\equiv 1\left(modp\right)$

Tomemos la secuencia de $p-1$ números:

$1\cdot a,2\cdot a,3\cdot a,\dots ,\left(p-1\right)\cdot a$

Si multiplicamos todos los miembros de la secuencia:

$\left(1\cdot a\right)\cdot \left(2\cdot a\right)\cdot \left(3\cdot a\right)\cdot \dots \cdot \left(\left(p-1\right)\cdot a\right)=\left(p-1\right)!\cdot a^{p-1}$

Además, sabemos que todos los números de la secuencia son diferentes, $modp$.

Lo anterior se desprende del hecho de que si $r\cdot a\equiv s\cdot a\left(modp\right)$, entonces $r\equiv s\left(modp\right)$, puesto que $a$ es coprimo con $p$.

Así que tenemos $p-1$ números, menores que $p$, todos diferentes y ninguno $0\left(modp\right)$.

Por lo tanto deben ser congruentes a $\left\{1,2,3,\dots ,\left(p-1\right)\right\}\left(modp\right)$ en algún orden.

Así que su producto debe ser congruente con $\left(p-1\right)!\left(modp\right)$.

Igualando las expresiones:

$\left(p-1\right)!\cdot a^{p-1}=\left(p-1\right)!\left(modp\right)$

Puesto que $\left(p-1\right)!$ es coprimo con $p$:

$a^{p-1}\equiv 1\left(modp\right)$

Q.E.D.

---

Ejemplos:

a)$¿3^6\equiv 1\left(mod7\right)?$

La secuencia de 7-1 = 6 números es:

$\left(1\cdot 3\right),\left(2\cdot 3\right),\left(3\cdot 3\right),\left(4\cdot 3\right),\left(5\cdot 3\right),\left(6\cdot 3\right)=3,6,9,12,15,18$

en $mod7$:

$3,6,2,5,1,4$

aunque en otro orden, es equivalente a

$1,2,3,4,5,6$

Multiplicando los elementos de la primer secuencia:

$3\cdot 6\cdot 9\cdot 12\cdot 15\cdot 18=\left(6!\right)\cdot 3^6$

y los de la segunda:

$1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=\left(6!\right)$

Igualando $\left(mod7\right)$:

$\left(6!\right)\cdot 3^6\equiv \left(6!\right)\left(mod7\right)$

$3^6=729\equiv 1\left(mod7\right)$

---

b)$¿3^5\equiv 1\left(mod6\right)?$ (6 no es primo, ni coprimo con 3)

$\left(1\cdot 3\right),\left(2\cdot 3\right),\left(3\cdot 3\right),\left(4\cdot 3\right),\left(5\cdot 3\right)=3,6,9,12,15$

en $mod6$:

$3,0,3,0,3$

si multiplicamos los elementos:

$0\ne 5!$ El teorema no se puede aplicar.

---

c)$¿5^7\equiv 1\left(mod8\right)?$ (8 no es primo, pero es coprimo con 5)

$\left(1\cdot 5\right),\left(2\cdot 5\right),\left(3\cdot 5\right),\left(4\cdot 5\right),\left(5\cdot 5\right),\left(5\cdot 6\right),\left(5\cdot 7\right)=5,10,15,20,25,30,35$

en $mod8$:

$5,2,7,4,1,6,3$

multiplicando los elementos:

$5\cdot 2\cdot 7\cdot 4\cdot 1\cdot 6\cdot 3=7!$, pero puesto que 8 no es primo

$7!\equiv 0\left(mod8\right)$, ya que 7! contiene los factores primos de 8.

Finalmente, tendríamos:

$0\cdot 5^7\equiv 0\left(mod8\right)$, de donde nada podría concluirse.

El teorema no se puede aplicar.