[skip-to-content]

Sección 3.4 Pequeño Teorema de Fermat y Pseudoprimos

El siguiente resultado es una obra notable de Pierre de Fermat. ¡Será muy útil a la hora de calcular exponenciación modular!

Sea \(a \in \mathbb{Z}\text{.}\) Considere los primeros \(p-1\) múltiplos positivos de \(a\text{;}\) los cuales corresponden a \(a,2a,3a,...,(p-1)a\text{.}\) El resto de dividir los \(p-1\) múltiplos positivos de \(a\) por \(p\) corresponden a \(1,2,3,...,p-1\) en cierto orden. Multiplicando todas las congruencias involucradas, se consigue
\begin{equation*} a^{p-1}\cdot (p-1)!\equiv (p-1)! \ (\text{mod } p). \end{equation*}
Por otro lado, es sabido que \(p\not\mid (p-1)!\text{.}\) Por consiguiente \((p,(p-1)!)=1\text{.}\) De esta forma, se puede cancelar la expresión \((p-1)!\) (Proposición 3.1.10). Así
\begin{equation*} a^{p-1} \equiv 1 \ (\text{mod } p). \end{equation*}

Si \(p |a\text{,}\) entonces \(a^{p} \equiv 0 \equiv a \ (\text{mod } p)\text{.}\)

Si \(p\not\mid a\text{,}\) Por Teorema 3.4.1, se sabe que

\begin{equation*} a^{p-1} \equiv 1 \ (\text{mod } p), \end{equation*}
con \(a \in \mathbb{Z}\) y \(p\) primo, tal que \((a,p)=1\text{.}\) Multiplicando por \(a\text{,}\) se obtiene
\begin{equation*} a^{p} \equiv a \ (\text{mod } p). \end{equation*}

¿Cómo podemos utilizar el Pequeño Teorema de Fermat? ¡Veamos unos ejemplos!

Determine todos los enteros \(x\) que satisfacen la congruencia
\begin{equation*} x^{86} \equiv 6 \ (\text{mod } 29). \end{equation*}
Supondremos que \(x < 29\text{.}\) Como mcd \((x,29)=1\text{,}\) por Pequeño teorema de Fermat \(x^{28}\equiv 1 \ (\text{mod } 29)\text{.}\) Por Propiedad de Congruencias, se consigue \(x^{84}\equiv 1 \ (\text{mod } 29).\) Por lo tanto \(x^{86}\equiv x^{2} \ (\text{mod } 29).\) Además, \(6\equiv 64\) (mod \(29\)). Por transitividad, sólo basta resolver
\begin{equation*} x^{2}\equiv 64 \ (\text{mod } 29)\text{.} \end{equation*}
Por definición de Congruencia, \(29|(x-8)(x+8)\text{.}\) Como \(29\) es primo, por Lema de Euclides: \(29|(x-8)\) o \(29|(x+8)\text{.}\) Es decir, \(x\equiv 8 \ (\text{mod } 29)\) y \(x\equiv -8 \equiv 21 \ (\text{mod } 29).\)

Por lo tanto, las soluciones son \(\left[ 8\right]_{29}\) y \(\left[ 21\right]_{29}\text{.}\)

Si \(p,q\) son primos distintos tales que \(d=(p-1,q-1)\) y \(a\not\mid p\text{,}\) \(a\not\mid q\) entonces probaremos que
\begin{equation*} a^{(p-1)(q-1)/d}\equiv 1 \ (\text{mod } pq)\text{.} \end{equation*}
En efecto, ya que \(d=(p-1,q-1)\text{,}\) entonces \(d|(p-1)\) y \(d|(q-1)\text{.}\) Esto permite justificar que \(\frac{p-1}{d}\) y \(\frac{q-1}{d}\) son números enteros. Por Pequeño Teorema de Fermat, \(a^{p-1}\equiv 1 \ (\text{mod } p).\) Por lo tanto
\begin{equation*} a^{(p-1)(q-1)/d}\equiv 1 \ (\text{mod } p). \end{equation*}

Nuevamente, por Pequeño Teorema de Fermat, \(a^{q-1}\equiv 1 \ (\text{mod } p).\) Por consiguiente

\begin{equation*} a^{(p-1)(q-1)/d}\equiv 1 \ (\text{mod } q). \end{equation*}

Como \(p\) y \(q\) son primos distintos, entonces

\begin{equation*} a^{(p-1)(q-1)/d}\equiv 1 \ (\text{mod } pq)\text{.} \end{equation*}
Demuestre que \(2222^{5555}+5555^{2222}\) es divisible por 7.

¿Es posible encontrar números compuestos que satisfagan el Pequeño Teorema de Fermat? La Definición 3.4.6 tiene la respuesta.

Definición 3.4.6.
Se denomina pseudoprimo o número de Carmichael al entero compuesto \(n\) tal que \(a^{n} \equiv a\) (mod \(n\)), para todo \(a \in \mathbb{Z}\text{.}\)
Observación 3.4.7.
Note que \(n\) también es un pseudoprimo o número de Carmichael si satisface \(a^{n-1} \equiv 1\) (mod \(n\)), para todo \(a \in \mathbb{Z}\text{,}\) \(n \in \mathbb{N}\) y \((a,n)=1\text{.}\)

¿Existirá algún criterio para determinar si un número compuesto \(n\) es de Carmichael? ¡Si! (La Proposición 3.4.8 exhibe un resultado parcial).

Sea \(i=1,2,...,r\) y \(a\text{,}\) un número entero cualquiera. Supondremos que \(p_{i}\not\mid a\text{;}\) por lo que \((a,p_{i})=1\text{.}\) Por Pequeño Teorema de Fermat
\begin{equation*} a^{p_{i}-1}\equiv 1 \ (\text{mod } p_{i}). \end{equation*}

Por hipótesis, \((p_{i}-1)|(n-1)\text{.}\) Entonces

\begin{equation*} a^{n-1}\equiv 1 \ (\text{mod } p_{i}). \end{equation*}
Esto implica \(a^{n-1}\equiv 1 \ (\text{mod } n)\text{.}\) Por lo tanto, \(a^{n}\equiv a \ (\text{mod } n).\)

Si \(p_{i}|a_{i}\text{,}\) entonces \(a^{n}\equiv a \ (\text{mod } p_{i})\text{.}\) Por consiguiente, \(a^{n}\equiv a \ (\text{mod } n)\text{.}\)

De esta forma, \(n\) es un número de Carmichael.

Probaremos que \(561\)es un Número de Carmichael. Se sabe que \(561=3\cdot 11\cdot 17\text{.}\) Por Proposición 5.4.7: \(2|560\text{,}\) \(10|560\)y \(16|560\text{.}\)

Por lo tanto, \(561\) es un Número de Carmichael (¡es el más pequeño!).

Pruebe que \(10585\) es un Número de Carmichael.
Observación 3.4.11.
Existen infinitos Números de Carmichael.
Observación 3.4.12.
Los Números de Carmichael son muy escasos. ¡Sólo 43 de ellos son menores que un millon!

El siguiente interact de Sage permite verificar si el Pequeño Teorema de Fermat se cumple para un número primo o compuesto \(n\) (debe seleccionar \(a\)).