El pequeño teorema de Fermat establece que si p es un número primo , entonces para cualquier número 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 una no es divisible por p , pequeño teorema de Fermat es equivalente a la afirmación de que un 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, por tanto, un múltiplo de 7.
El pequeño teorema de Fermat es la base de la prueba de primordialidad de Fermat y es uno de los resultados fundamentales de la teoría de números elemental . El teorema lleva el nombre de Pierre de Fermat , quien lo declaró en 1640. Se llama el "pequeño teorema" para distinguirlo del último teorema de Fermat . [3]
Historia
Pierre de Fermat enunció 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 un 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 quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.
Esto se puede traducir, con explicaciones y fórmulas agregadas entre paréntesis para facilitar la comprensión, como:
Cada número primo [ p ] divide necesariamente una de las potencias menos una 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 el primo dado menos uno [divide p - 1 ]. Una vez que se ha encontrado la primera potencia [ t ] que satisface la pregunta, todos aquellos cuyos exponentes son múltiplos del exponente del primero satisfacen de manera similar la pregunta [es decir, todos los múltiplos del primer t tienen la misma propiedad].
Fermat no consideró el caso en el que a es un múltiplo de p ni probó su afirmación, solo afirmando: [4]
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.
(Y esta proposición es generalmente cierta para todas las series [ sic ] y para todos los números primos; le enviaría una demostración, si no tuviera miedo de continuar por mucho tiempo). [5]
Euler proporcionó la primera prueba publicada en 1736, en un artículo titulado "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" en las Actas de la Academia de San Petersburgo, [6] pero Leibniz había dado prácticamente la misma prueba en un manuscrito inédito de algún tiempo antes. 1683. [3]
El término "pequeño teorema de Fermat" probablemente fue utilizado por primera vez en forma impresa en 1913 en Zahlentheorie por Kurt Hensel :
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.
(Hay un teorema fundamental que se sostiene en cada grupo finito, generalmente llamado el pequeño teorema de Fermat porque Fermat fue el primero en haber demostrado una parte muy especial de él).
Un uso temprano en Inglés ocurre en AA Albert 's moderna álgebra superior (1937), que se refiere a 'la llamada 'pequeño' teorema de Fermat' en la página 206. [7]
Más historia
Algunos matemáticos formularon independientemente la hipótesis relacionada (a veces llamada incorrectamente la 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 pseudoprime . Vea a continuación .
Pruebas
Se conocen varias pruebas del pequeño teorema de Fermat. Con frecuencia se demuestra como un corolario del teorema de Euler .
Generalizaciones
El teorema de Euler es una generalización del pequeño teorema de Fermat: para cualquier módulo n y cualquier entero una primos entre sí a n , uno tiene
donde φ ( n ) denota la función totient de Euler (que cuenta los números enteros de 1 a n , que son primos entre sí a 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 cualquier enteros x e y . Esto se sigue del teorema de Euler, ya que, si, entonces x = y + kφ ( n ) para algún entero k , y uno tiene
Si n es primo, esto también es un corolario del pequeño teorema de Fermat. Esto se usa ampliamente en aritmética modular , porque permite reducir la exponenciación modular con grandes exponentes a exponentes menores que n .
Si n no es primo, se usa en criptografía de clave pública , generalmente en el criptosistema RSA de la siguiente manera: [8] si
la recuperación de x de los valores de e y n es fácil si uno sabe φ ( n ) . De hecho, el algoritmo euclidiano extendido permite calcular el inverso modular de e módulo φ ( n ) , que es el entero f tal. Resulta que
Por otro lado, si n = pq es el producto de dos números primos distintos, entonces φ ( n ) = ( p - 1) ( q - 1) . En este caso, la búsqueda de f de n y e es tan difícil como la informática φ ( n ) (esto no se ha probado, pero ningún algoritmo es conocido para el cálculo de f sin saber φ ( n ) ). Conociendo solamente 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 por el contrario, los factores de p y q son los ( entero) soluciones de la ecuación x 2 - ( n - φ ( n ) + 1) x + n = 0 .
La idea básica del criptosistema RSA es así: si un mensaje x está encriptado como y = x e (mod n ) , usando valores públicos de n y e , entonces, con el conocimiento actual, no se puede desencriptar sin encontrar el (secreto) factores 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 .
Conversar
Lo contrario del pequeño teorema de Fermat no es generalmente cierto, ya que falla para los números de Carmichael . Sin embargo, una forma ligeramente más fuerte del teorema es verdadera y se conoce como teorema de Lehmer. El teorema es el siguiente:
Si existe un entero un tal que
y para todos los primos q dividiendo p - 1 uno tiene
entonces p es primo.
Este teorema forma la base de la prueba de primalidad de Lucas , una prueba de primordialidad importante .
Pseudoprimes
Si una y p son números coprimas tal que un p -1 - 1 es divisible por p , entonces p no tiene que ser primordial. Si no es así, entonces p se llama pseudoprime (Fermat) a la base a . El primer pseudoprime a base 2 fue encontrado en 1820 por Pierre Frédéric Sarrus : 341 = 11 × 31. [9] [10]
Un número p que es un pseudoprime Fermat a base de una para cada número una primos entre sí a p se llama un número de Carmichael (por ejemplo 561). Alternativamente, cualquier número p que satisfaga la igualdad
es un número primo o de Carmichael.
Prueba de primaria de Miller-Rabin
La prueba de primalidad de Miller-Rabin utiliza la siguiente extensión del pequeño teorema de Fermat: [11]
Si p es un número impar de primera, y p - 1 = 2 s d , con d impar, entonces para cada una privilegiada para p , ya sea un d ≡ 1 mod p , o existe t tal que 0 ≤ t
y una 2 t d ≡ −1 mod p
Este resultado se puede deducir 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 campo finito , en el que 1 tiene exactamente dos raíces cuadradas, 1 y -1.
La prueba de Miller-Rabin usa esta propiedad de la siguiente manera: dado p = 2 s d + 1 , con d impar, un número entero impar para el que se debe probar la primalidad, elija aleatoriamente a tal que 1 < a < p ; luego calcule b = a d mod p ; si b no es 1 ni −1, entonces eleve al cuadrado repetidamente módulo p hasta que obtenga 1, −1, o tenga s veces al cuadrado . Si no se ha obtenido b ≠ 1 y −1, entonces p no es primo. De lo contrario, p puede ser primo o no. Si p no es primo, la probabilidad de que la prueba lo demuestre es superior a 1/4. Por lo tanto, después de k pruebas aleatorias no concluyentes, la probabilidad de que p no sea primo es menor que (3/4) k y, por lo tanto, puede hacerse tan baja como se desee, aumentando k .
En resumen, la prueba prueba que un número no es primo o afirma que es primo con una probabilidad de error que puede elegirse tan baja como se desee. La prueba es muy simple de implementar y computacionalmente más eficiente que todas las pruebas deterministas conocidas. Por lo tanto, generalmente se usa antes de comenzar una prueba de primalidad.
Ver también
- Cociente de Fermat
- Endomorfismo de Frobenius
- p -derivación
- Fracciones con denominadores primos : números con comportamiento relacionado con el pequeño teorema de Fermat
- RSA
- Tabla de congruencias
- Inverso multiplicativo modular
Notas
- ^ Long 1972 , págs. 87–88.
- ^ Pettofrezzo y Byrkit 1970 , págs. 110-111.
- ↑ a b c Burton , 2011 , p. 514.
- ↑ Fermat, Pierre (1894), Curtiduría, P .; Henry, C. (eds.), Oeuvres de Fermat. Tomo 2: Correspondencia , París: Gauthier-Villars, págs. 206–212 (en francés)
- ^ Mahoney 1994 , p. 295 para la traducción al inglés
- ^ Mineral de 1988 , p. 273
- ↑ Albert , 2015 , p. 206
- ^ Trappe, Wade; Washington, Lawrence C. (2002), Introducción a la criptografía con teoría de la codificación , Prentice-Hall, p. 78, ISBN 978-0-13-061814-6
- ^ Sloane, N. J. A. (ed.). "Secuencia A128311 (resto en la división de 2 n -1 -1 por n .)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Sarrus, Frédéric (1819-1820). "Demonstration de la fausseté du théorème énoncé á la página 320 du IXe volume de ce recueil" [Demostración de la falsedad del teorema enunciado en la página 320 del noveno volumen de esta colección]. Annales de Mathématiques Pures et Appliquées (en francés). 10 : 184-187.
- ^ Rempe-Gillen, Lasse; Waldecker, Rebecca (11 de diciembre de 2013). "4.5.1. Lema (Raíces de unidad módulo a prima)" . Prueba de primordialidad para principiantes . American Mathematical Soc. ISBN 9780821898833.
Referencias
- Albert, A. Adrian (2015) [1938], Álgebra superior moderna , Cambridge University Press , ISBN 978-1-107-54462-8
- Burton, David M. (2011), La Historia de las Matemáticas / Una Introducción (7a ed.), McGraw-Hill, ISBN 978-0-07-338315-6
- Long, Calvin T. (1972), Introducción elemental a la teoría de números (2a ed.), Lexington: DC Heath and Company , LCCN 77171950
- Mahoney, Michael Sean (1994), La carrera matemática de Pierre de Fermat, 1601–1665 (2ª ed.), Princeton University Press, ISBN 978-0-691-03666-3
- Ore, Oystein (1988) [1948], Teoría de números y su historia , Dover, ISBN 978-0-486-65620-5
- Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Elementos de la teoría de números , Englewood Cliffs: Prentice Hall , LCCN 71081766
Otras lecturas
- Paulo Ribenboim (1995). El nuevo libro de registros de números primos (3ª ed.). Nueva York: Springer-Verlag. ISBN 0-387-94457-5 . págs. 22-25, 49.
enlaces externos
- Medios relacionados con el pequeño teorema de Fermat en Wikimedia Commons
- Teorema de Fermat en la Encyclopædia Britannica
- János Bolyai y los pseudoprimes (en húngaro)
- Pequeño teorema de Fermat en el corte del nudo
- Función y teorema de Euler al cortar el nudo
- El pequeño teorema de Fermat y la prueba de Sophie
- "El pequeño teorema de Fermat" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Weisstein, Eric W. "El pequeño teorema de Fermat" . MathWorld .
- Weisstein, Eric W. "El pequeño teorema inverso de Fermat" . MathWorld .