Pequeño teorema de Fermat

Enviado por jesus el 17 de Mayo de 2009 - 12:41.

Todo número $ a$ no divisible por un primo $ p$ deja residuo 1 al elevarse a la potencia $p-1$ y dividirse entre $p$. En términos de congruencias, esto se escribe así:

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

Otra forma de presentar este teorema es multiplicando por $ a$:

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

En esta otra forma se puede omitir la condición de que $ a$ no es divisible entre $ p$, puesto que, cuando $ p$ divide a $ a$, ambos lados de la identidad anterior son cero.

Demostración(es)

Demostración:

Consideremos los números $a, 2a, 3a, \dots , (p-1)a$. Cada uno de éstos número tiene distinto residuo [1] al dividir entre $ p$. Ya que, si $ia \equiv ja \pmod{p}$ y como $ p$ y $ a$ son primos relaivos [2] (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 [1] 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] $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 [2] 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} $$