Pequeño teorema 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, con a>0 , ap ≡ a (mod p)
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, con a>0 , coprimo con p , ap-1 ≡ 1 (mod p)
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 solo una conjetura durante 350 años y finalmente fue demostrado por Andrew Wiles en 1995.
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 2p − 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 2p ≡ 2 (mod p) (donde el símbolo ≡ significa congruencia según el módulo indicado). Es verdad que, si p es primo, entonces 2p ≡ 2 (mod p) (este es un caso especial del pequeño teorema de Fermat), pero el recíproco (si 2p ≡ 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 ap-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.
Fermat estableció tal resultado en una carta a Frénicle de Bessy, pero como era habitual en él, omitió la prueba del mismo:
La primera demostración publicada se debe a Leonhard Euler en 1736 en un artículo titulado Theorematum Quorundam ad Numeros 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 solo 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 n1 a n+1, se cumple para n1 y n1+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 es divisible por p, para todo n, tal que 1≤ n<p. Esto es así puesto que el coeficiente binomial se define como:
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, estos 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:
A continuación se muestran algunos ejemplos del teorema:
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.
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:
Utilizando un método análogo, Euler invalidó la única conjetura falsa de Fermat, la cual decía que todo número de la forma Fn = 22n + 1, (con n natural), es primo. (números de Fermat).
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.
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. Este 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.
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, ap-1 - 1 sea divisible por p, o sea, que ap-1 sea congruente con uno módulo p (en notación moderna como ap - 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 an-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:
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.
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.
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 ap-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 solo se cumplen para una base a concreta, por ejemplo, si a es igual a 2, 341 cumple que 2341-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 sea primo, debido a los pseudoprimos o al número de comprobaciones.
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 am ≡ an (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:
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:
donde ahora λ(n) es la función de Carmichael.