Pequeño teorema de Fermat

Pierre de Fermat.

El pequeño teorema de Fermat es uno de los teoremas clásicos de teoría de números relacionado con la divisibilidad. Se formula de la siguiente manera:

Si p es un número primo, entonces, para cada número natural a , ap ≡ a (mod p) Pierre de Fermat, 1636

Aunque son equivalentes, el teorema suele ser presentado de esta otra forma:

Si p es un número primo, entonces, para cada número natural a coprimo con p , ap-1 ≡ 1 (mod p) Pierre de Fermat, 1636

Esto quiere decir que, si se eleva un número a a la p-ésima potencia y al resultado se le resta a, lo que queda es divisible por p (véase aritmética modular). Su interés principal está en su aplicación al problema de la primalidad y en criptografía.

Este teorema no tiene nada que ver con el legendario último teorema de Fermat, que fue sólo una conjetura durante 350 años y finalmente fue demostrado por Andrew Wiles en 1995.​

Historia

La civilización china parece que fue la primera cultura en estar interesada en la aritmética modular.​ Existe una hipótesis,​ documentada por Joseph Needham, según la cual los números de la forma 2^p − 2 fueron estudiados por esta civilización.

Así pues, matemáticos chinos formularon la hipótesis (a veces conocida como hipótesis china) de que p es primo si y sólo si 2^p ≡ 2 (mod p) (donde el símbolo ≡ significa congruencia según el módulo indicado). Es verdad que, si p es primo, entonces 2^p ≡ 2 (mod p) (este es un caso especial del pequeño teorema de Fermat), pero el recíproco (si 2^p ≡ 2 (mod p), entonces p es primo) no lo es, por lo que la hipótesis es falsa.

Se cree ampliamente que la hipótesis china fue desarrollada 2000 años antes del trabajo de Fermat en el siglo XVII. Aunque la hipótesis sea parcialmente incorrecta, es notable que pueda haber sido conocida por los matemáticos de la antigüedad. Algunos, sin embargo, sostienen que la creencia de que esta hipótesis fuera conocida hace tanto tiempo es fruto de un error de comprensión, y que se desarrolló realmente en 1872. Para más información sobre este asunto, consúltese (Ribenboim, 1995).

Alrededor de 1636, Pierre de Fermat enunció el teorema. Aparece en una de sus cartas a su confidente Frénicle de Bessy, fechada el 18 de octubre de 1640, con el siguiente texto: p divide a a^p-1 - 1 cuando p sea primo y a sea coprimo con p.​

Aunque actualmente lo conozcamos como pequeño teorema de Fermat, lo cierto es que hasta el siglo XX fue conocido como teorema de Fermat, como recoge por ejemplo Carl Friedrich Gauss en su libro Disquisitiones arithmeticae.​ El término pequeño teorema de Fermat, tal como lo conocemos actualmente, fue usado por primera vez por el matemático alemán Kurt Hensel en 1913 en su libro Zahlentheorie.​

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.

He aquí el teorema fundamental que se cumple en cada grupo finito, llamado habitualmente pequeño teorema de Fermat, porque Fermat fue el primero en probar una parte especial de él.

Kurt Hensel

Demostración

Fermat estableció tal resultado en una carta a Frénicle de Bessy, pero como era habitual en él, omitió la prueba del mismo:​

Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné -1. (...) Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

Todo número primo mide una de las potencias menos uno de cualquier progresión en la que el exponente es un múltiplo del primo dado menos uno. (...) Y esta proposición es generalmente cierta para todas las progresiones y todos los números primos; le enviaría la prueba, si no temiese que es demasiado larga.

Pierre de Fermat

Leonhard Euler daría la primera demostración formal del teorema en 1736.

La primera demostración publicada se debe a Leonhard Euler en 1736 en un artículo titulado Theorematum Quorundam ad Números Primos Spectantium Demonstratio.​ Daría otras dos demostraciones más a lo largo de su vida,​ aunque era la primera de todas ellas la misma que había en un manuscrito personal de Gottfried Leibniz, escrito sobre 1683 y que nunca llegó a publicar.​ Gauss publicaría otra prueba más en su libro Disquisitiones arithmeticae en 1801.​​

La prueba original de Euler (y Leibniz) es sencilla, en términos de comprensión lógica, ya que sólo utiliza métodos elementales que una persona con nociones básicas de álgebra puede entender. Su demostración se basa en el principio de inducción, que consiste en demostrar que si cierta propiedad P de los números naturales se cumple para n y también se cumple para n+1, entonces se cumple para todo n.​ Es fácil ver que si se cumple para n, y para n+1, también se cumple para n+2, n+3, etc. ya que, llamando como n₁ a n+1, se cumple para n₁ y n₁+1, por tanto, para n, n+1 y n+2, y así sucesivamente.

Para la demostración también se utiliza la propiedad de que si p es un número primo, entonces el coeficiente binomial $\textstyle {p \choose n}$ es divisible por p, para todo n, tal que 1≤ n<p. Esto es así puesto que el coeficiente binomial se define como:

${p \choose n}={\frac {p!}{(p-n)!\cdot n!}}$

Donde el signo ! corresponde al factorial de un número, que indica la multiplicación de todos los números naturales menores o iguales a dicho número, por ejemplo, p! = p·(p-1)·(p-2)·...·2·1. Puesto que en el denominador, los factoriales de los números involucran números que son menores que el número primo p, éstos no pueden contener p ni dividir al número primo p del numerador, así pues, el coeficiente es divisible por p.

Dicho esto, la demostración consiste en los siguientes pasos:

• Supongamos que $\textstyle {p\mid n^{p}-n}\,\!$

• Utilizamos el binomio de Newton para expandir la potencia (n + 1)^p:

$(n+1)^{p}=\sum _{k=0}^{p}{p \choose k}n^{p-k}$

• Agrupando factores y reordenando la identidad:

$(n+1)^{p}-(n+1)=n^{p}-n+\sum _{k=1}^{p-1}{p \choose k}n^{p-k}$

• Por hipótesis, hemos supuesto que n^p - n es divisible por p, y dado que todos los términos del sumatorio del miembro de la derecha son divisibles por p, tenemos que p divide a (n + 1)^p - (n + 1).

• Ahora bien, 1^p - 1 es divisible por p, por lo tanto 2^p - 2 también es divisible por p, y así sucesivamente.

Q.E.D.

Ejemplos

A continuación se muestran algunos ejemplos del teorema:

• 5³ − 5 = 120 es divisible por 3.
• 7² − 7 = 42 es divisible por 2.
• 2⁵ − 2 = 30 es divisible por 5.
• (−3)⁷ + 3 = − 2.184 es divisible por 7.
• 2⁹⁷ − 2 = 158.456.325.028.528.675.187.087.900.670 es divisible por 97.

Aplicaciones

Las aplicaciones son numerosas, particularmente en criptografía. No obstante, hay ejemplos clásicos de aplicaciones del teorema en matemáticas puras, sobre todo, relacionadas con el problema de la primalidad.

Aplicaciones teóricas

El pequeño teorema de Fermat se ha utilizado históricamente para analizar la descomposición en producto de factores primos de ciertos enteros. Así, Fermat escribió a Marin Mersenne:​

Vous me demandez si le nombre 100.895.598.169 est premier ou non, et une méthode pour découvrir, dans l'espace d'un jour, s'il est premier ou composé. A cette question, je réponds que ce nombre est composé et se fait du produit de ces deux: 898.423 et 112.303, qui sont premiers.

Usted me pregunta si el número 100.895.598.169 es primo o no, y un método para descubrir, en el plazo de un día, si es primo o compuesto. A esta pregunta, yo le respondo que este número es compuesto y que se obtiene del producto de estos dos: 898.423 y 112.303, que son primos.

Pierre de Fermat

Utilizando un método análogo, Euler invalidó la única conjetura falsa de Fermat, es decir, que los números de Fermat no son todos primos.​

Este teorema también se ha utilizado para demostrar resultados de la teoría de números algebraicos, como el teorema de Herbrand-Ribet. Ha sobrepasado el ámbito estricto de la aritmética, con una utilización para el estudio de los puntos fijos del Endomorfismo de Frobenius, por ejemplo.

Criptografía asimétrica

La criptografía con clave pública corresponde a un código que se agrega para asegurar la confidencialidad de los mensajes con la ayuda de dos claves criptográficas. Una, que permite cifrar el mensaje, es pública. La otra, que tiene como objetivo el descifrado, es privada.

Una importante familia de códigos asimétricos utiliza la tecnología llamada RSA. La clave secreta está determinada por la descomposición de un número entero grande, a menudo de varias centenas de cifras. Éste tiene dos factores primos. Lo esencial de las técnicas industriales de principios del siglo XXI se basa en el pequeño teorema de Fermat para generar grandes números primos o para comprobar la primalidad de un número.

Test de primalidad

El pequeño teorema de Fermat da una condición necesaria para que un número p sea primo. Es necesario que, para todo número natural a menor que p, a^p-1 - 1 sea divisible por p, o sea, que a^p-1 sea congruente con uno módulo p (en notación moderna como a^{p - 1} ≡ 1 (mod p)). Este principio es la base del test de primalidad de Fermat.​ Este test, al que asumimos una entrada n, consiste en ir probando que a^n-1 ≡ 1 (mod n) para una serie de valores de a, tales que sean menores que n. Si n es primo, entonces la congruencia se cumplirá siempre (condición necesaria del teorema) mientras que si n es compuesto, la congruencia puede no cumplirse. Si para algún valor de a (menor que n) no se cumple la congruencia, entonces n es compuesto. Una descripción de este test de forma general, en forma de algoritmo escrito en pseudocódigo, podría ser la siguiente:

Algoritmo Test de primalidad de Fermat.

Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test. Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo. Para $j\,\!$ desde $1\,\!$ hasta $k\,\!$ haga lo siguiente: $a\gets$ Función genera un número aleatorio comprendido entre $1\,\!$ y $n\,\!$ (sin incluirlos) Si $a^{n-1}\not \equiv 1{\pmod {n}}$ entonces: Retorne COMPUESTO Retorne POSIBLE PRIMO

Existen numerosas variantes algorítmicas que usan como base este test. Las más conocidas son el test de primalidad de Solovay-Strassen y sobre todo el test de primalidad de Miller-Rabin.

Número pseudoprimo

Los tests precedentes utilizan una condición necesaria pero no suficiente. Tanto es así que existen números enteros p compuestos y coprimos con a tal que a ^p-1 es congruente con uno modulo p, son los llamados pseudoprimos.​ Estos números tienen la peculiaridad de que pueden pasar el test de primalidad de Fermat algunas veces, siendo reconocidos como falsos primos. Existen varias clases de pseudoprimos, por ejemplo, los que cumplen que a^p-1 ≡ 1 (mod p) para todos los valores de a que sean coprimos con p, siendo p compuesto se denominan números de Carmichael. El número 1729 es un ejemplo de número de Carmichael. Además existen otros pseudoprimos que sólo se cumplen para una base a concreta, por ejemplo, si a es igual a 2, 341 cumple que 2^341-1 ≡ 1 (mod 341), siendo 341 claramente compuesto.

Los tests indicados en la sección anterior son todos estadísticos, en el sentido de que existe siempre una probabilidad, a veces muy débil, de que el número que ha pasado el test no es primo, debido a los pseudoprimos o al número de comprobaciones.

Generalizaciones

Una pequeña generalización del teorema, que se sigue de él, dice lo siguiente: si p es primo y m y n son enteros positivos con m ≡ n (mod p-1), entonces a^m ≡ aⁿ (mod p) para todos los enteros a.​ Expresado así, el teorema se utiliza para justificar el método de cifrado de clave pública RSA.

El pequeño teorema de Fermat se puede generalizar mediante el teorema de Euler; para cualquier módulo n y cualquier entero a coprimo con n, se tiene:

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

donde φ(n) es la función φ de Euler que cuenta el número de enteros entre 1 y n coprimos con n. Esta es de hecho una generalización, ya que si n = p es un número primo, entonces φ(p) = p - 1.

Aun así, todavía se puede generalizar más, como así se muestra en el teorema de Carmichael. Como antes, para cualquier módulo n y cualquier entero a coprimo con n, se tiene:

$a^{\lambda (n)}\equiv 1{\pmod {n}}$

donde ahora λ(n) es la función de Carmichael.​

Véase también

• Aritmética modular
• Teorema de Euler
• Demostraciones del pequeño teorema de Fermat
• Teorema de Carmichael

Bibliografía

• Ribenboim, Paul (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5. 
• Gauss, Carl Friedrich (1965). Disquisitiones Arithmeticae, tr. Arthur A. Clarke. Yale University Press. ISBN 0-300-09473-6. 

Enlaces externos

• Weisstein, Eric W. «Fermat's Little Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Fermat's little theorem en PlanetMath.