En teoría de números , el pequeño teorema de Fermat establece que si p es un número primo , entonces, para cualquier entero a , el número a p − a es un múltiplo entero de p . En la notación de la aritmética modular , esto se expresa como
Por ejemplo, si a = 2 y p = 7 , entonces 2 7 = 128 , y 128 − 2 = 126 = 7 × 18 es un múltiplo entero de 7 .
Si a no es divisible por p , es decir, si a es coprimo de p , entonces el pequeño teorema de Fermat es equivalente a la afirmación de que a p − 1 − 1 es un múltiplo entero de p , o en símbolos: [1] [2]
Por ejemplo, si a = 2 y p = 7 , entonces 2 6 = 64 , y 64 − 1 = 63 = 7 × 9 es un múltiplo de 7 .
El pequeño teorema de Fermat es la base de la prueba de primalidad de Fermat y es uno de los resultados fundamentales de la teoría elemental de números . El teorema recibe su nombre de Pierre de Fermat , quien lo formuló en 1640. Se lo llama "pequeño teorema" para distinguirlo del último teorema de Fermat . [3]
Pierre de Fermat formuló por primera vez el teorema en una carta fechada el 18 de octubre de 1640 a su amigo y confidente Frénicle de Bessy . Su formulación es equivalente a la siguiente: [3]
Si p es un primo y a es cualquier número entero no divisible por p , entonces a p − 1 − 1 es divisible por p .
La declaración original de Fermat fue
Tout nombre premier mesure infailliblement une des puissances de quelquegression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ; y, después de haber encontrado la potencia del estreno que satisface la pregunta, todas las células no son exponentes múltiples de la exposición del estreno que satisfacen también a la pregunta.
Esto se puede traducir, con explicaciones y fórmulas agregadas entre paréntesis para una mejor comprensión, como:
Todo número primo [ p ] divide necesariamente a una de las potencias menos uno de cualquier progresión [geométrica] [ a , a 2 , a 3 , … ] [es decir, existe t tal que p divide a t – 1 ], y el exponente de esta potencia [ t ] divide al primo dado menos uno [divide a p – 1 ]. Después de haber encontrado la primera potencia [ t ] que satisface la cuestión, todos aquellos cuyos exponentes son múltiplos del exponente del primero satisfacen de forma similar la cuestión [es decir, todos los múltiplos del primer t tienen la misma propiedad].
Fermat no consideró el caso en que a es un múltiplo de p ni demostró su afirmación, limitándose a afirmar: [4]
Et esta proposición est généralement vraie en todas las progresiones y en todos los nombres premiers; De quoi je vous envoierois la demostración, si je n'appréhendois d'être trop long.
(Y esta proposición es generalmente verdadera para todas las series [ sic ] y para todos los números primos; te enviaría una demostración de ella, si no temiera extenderme demasiado.) [5]
Euler proporcionó la primera prueba publicada en 1736, en un artículo titulado "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" (en español: "Demostración de ciertos teoremas sobre números primos") en las Actas de la Academia de San Petersburgo, [6] [7] pero Leibniz había dado virtualmente la misma prueba en un manuscrito inédito de algún momento anterior a 1683. [3]
El término "pequeño teorema de Fermat" probablemente fue utilizado por primera vez en forma impresa en 1913 en Zahlentheorie de Kurt Hensel : [8]
Para cada grupo endliche 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.
(Existe un teorema fundamental que se cumple en cada grupo finito, usualmente llamado el pequeño teorema de Fermat porque Fermat fue el primero en demostrar una parte muy especial del mismo.)
Un uso temprano en inglés aparece en Modern Higher Algebra de AA Albert (1937), que se refiere al "llamado 'pequeño' teorema de Fermat" en la página 206. [9]
Algunos matemáticos formularon de forma independiente la hipótesis relacionada (a veces llamada incorrectamente hipótesis china) de que 2 p ≡ 2 (mod p ) si y solo si p es primo. De hecho, la parte "si" es verdadera y es un caso especial del pequeño teorema de Fermat. Sin embargo, la parte "solo si" es falsa: por ejemplo, 2 341 ≡ 2 (mod 341) , pero 341 = 11 × 31 es un pseudoprimo en base 2. Véase a continuación.
Se conocen varias demostraciones del pequeño teorema de Fermat. Con frecuencia se demuestra como corolario del teorema de Euler .
El teorema de Euler es una generalización del pequeño teorema de Fermat: para cualquier módulo n y cualquier entero a coprimo con n , se tiene
donde φ ( n ) denota la función totiente de Euler (que cuenta los números enteros de 1 a n que son coprimos con n ). El pequeño teorema de Fermat es de hecho un caso especial, porque si n es un número primo, entonces φ ( n ) = n − 1 .
Un corolario del teorema de Euler es: Para cada entero positivo n , si el entero a es coprimo con n , entonces para cualesquiera enteros x e y . Esto se deduce del teorema de Euler, ya que, si , entonces x = y + kφ ( n ) para algún entero k , y se tiene
Si n es primo, esto también es un corolario del pequeño teorema de Fermat. Esto se usa mucho en aritmética modular , porque permite reducir la exponenciación modular con exponentes grandes a exponentes menores que n .
El teorema de Euler se utiliza con n no primo en criptografía de clave pública , específicamente en el criptosistema RSA , típicamente de la siguiente manera: [10] si recuperar x de los valores de y , e y n es fácil si uno conoce φ ( n ) . [11] De hecho, el algoritmo euclidiano extendido permite calcular la inversa modular de e módulo φ ( n ) , es decir, el entero f tal que Se deduce que
Por otra parte, si n = pq es el producto de dos números primos distintos, entonces φ ( n ) = ( p − 1)( q − 1) . En este caso, hallar f a partir de n y e es tan difícil como calcular φ ( n ) (esto no se ha demostrado, pero no se conoce ningún algoritmo para calcular f sin conocer φ ( n ) ). Conociendo solo n , el cálculo de φ ( n ) tiene esencialmente la misma dificultad que la factorización de n , ya que φ ( n ) = ( p − 1)( q − 1) , y a la inversa, los factores p y q son las soluciones (enteras) de la ecuación x 2 – ( n − φ ( n ) + 1) x + n = 0 .
La idea básica del criptosistema RSA es la siguiente: si un mensaje x se cifra como y = x e (mod n ) , utilizando valores públicos de n y e , entonces, con el conocimiento actual, no se puede descifrar sin encontrar los factores (secretos) p y q de n .
El pequeño teorema de Fermat también está relacionado con la función de Carmichael y el teorema de Carmichael , así como con el teorema de Lagrange en la teoría de grupos .
El recíproco del pequeño teorema de Fermat falla para los números de Carmichael . Sin embargo, una variante ligeramente más débil del recíproco es el teorema de Lehmer :
Si existe un entero a tal que y para todos los primos q que dividen a p − 1 se tiene entonces p es primo.
Este teorema constituye la base de la prueba de primalidad de Lucas , una prueba de primalidad importante, y del certificado de primalidad de Pratt .
Si a y p son números coprimos tales que a p −1 − 1 es divisible por p , entonces p no necesita ser primo. Si no lo es, entonces p se llama pseudoprimo (de Fermat) en base a . El primer pseudoprimo en base 2 fue encontrado en 1820 por Pierre Frédéric Sarrus : 341 = 11 × 31. [12] [13]
Un número p que es un pseudoprimo de Fermat en base a para cada número a coprimo con p se denomina número de Carmichael . Alternativamente, cualquier número p que satisface la igualdad es un primo o un número de Carmichael.
La prueba de primalidad de Miller-Rabin utiliza la siguiente extensión del pequeño teorema de Fermat: [14]
Si p es un primo impar y p − 1 = 2 s d con s > 0 y d impar > 0, entonces para cada a coprimo con p , o bien a d ≡ 1 (mod p ) o bien existe r tal que 0 ≤ r < s y a 2 r d ≡ −1 (mod p ) .
Este resultado puede deducirse del pequeño teorema de Fermat por el hecho de que, si p es un primo impar, entonces los números enteros módulo p forman un cuerpo finito , en el que 1 módulo p tiene exactamente dos raíces cuadradas, 1 y −1 módulo p .
Nótese que a d ≡ 1 (mod p ) se cumple trivialmente para a ≡ 1 (mod p ) , porque la relación de congruencia es compatible con la exponenciación . Y a d = a 2 0 d ≡ −1 (mod p ) se cumple trivialmente para a ≡ −1 (mod p ) ya que d es impar, por la misma razón. Es por eso que uno usualmente elige un a aleatorio en el intervalo 1 < a < p − 1 .
La prueba de Miller-Rabin utiliza esta propiedad de la siguiente manera: dado un entero impar p para el cual se debe probar la primalidad, se escribe p − 1 = 2 s d con s > 0 y d impar > 0, y se elige un a aleatorio tal que 1 < a < p − 1 ; luego se calcula b = a d mod p ; si b no es 1 ni −1, entonces se eleva al cuadrado repetidamente módulo p hasta obtener −1 o haber elevado al cuadrado s − 1 veces. Si b ≠ 1 y −1 no se ha obtenido elevando al cuadrado, entonces p es un compuesto y a es un testigo de la composición de p . De lo contrario, p es un primo probable fuerte para la base a ; es decir, puede ser primo o no. Si p es compuesto, la probabilidad de que la prueba lo declare de todos modos como un primo probable fuerte es como máximo 1 ⁄ 4 , en cuyo caso p es un pseudoprimo fuerte y a es un mentiroso fuerte . Por lo tanto, después de k pruebas aleatorias no concluyentes, la probabilidad de que p sea compuesto es como máximo 4 − k , y puede hacerse tan baja como se desee aumentando k .
En resumen, la prueba demuestra que un número es compuesto o afirma que es primo con una probabilidad de error que puede elegirse tan baja como se desee. La prueba es muy sencilla de implementar y computacionalmente más eficiente que todas las pruebas deterministas conocidas. Por lo tanto, generalmente se utiliza antes de comenzar una prueba de primalidad.
Medios relacionados con El pequeño teorema de Fermat en Wikimedia Commons
