El pequeño teorema de Fermat

El Pequeño Teorema de Fermat es un teorema de teoría de números que establece que [1] :

Si es un número primo y es un número entero no divisible por entonces es divisible por $pags$ $a$ $pags,$ $a^{p-1}-1$ $pags.$

En el lenguaje de la teoría de las congruencias : congruente a 1 módulo a primo . Notación formal: $a^{p-1}$ $pags$ $a^{p-1}\equiv 1{\pmod {p}}$

Por ejemplo, si entonces y $a=2;p=7,$ $2^{6}=64,$ $64-1=63=7\cpunto 9.$

El pequeño teorema de Fermat es un caso especial del teorema de Euler [2] , que a su vez es un caso especial del teorema de Carmichael y del teorema del grupo de Lagrange para grupos cíclicos finitos . El teorema fue enunciado sin demostración por Pierre Fermat , la primera demostración la dieron Leonhard Euler y Gottfried Wilhelm Leibniz .

El Pequeño Teorema de Fermat se ha convertido en uno de los principales teoremas para la investigación no sólo en la teoría de los números enteros, sino también en áreas más amplias [3] [4] .

Historia

Pierre Fermat formuló el enunciado original del teorema en una carta de 1640 al matemático francés Bernard Frenicle [5] :

Cada número primo es equivalente a [original: mide ] una potencia menos uno con cualquier base y un exponente igual al número primo dado menos uno... Y esta afirmación es generalmente cierta para todas las bases y todos los números primos. Te enviaría la prueba si no fuera tan larga.

Texto original (fr.)[ mostrarocultar] Tout nombre premier mesure infailliblement une des puissances −1 de quelque progresión que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné −1… Et cette proposición est généralement vraie en toutes progresiones et en tous nombres premiers ; de quoi je vous envoierois la demostración, si je n'appréhendois d'être trop long. — Fuente: Fermat a Frenicle

Como ejemplo, Fermat da la progresión 3, 9, 27, 81, 243, 729… y el número primo 13. 13 divide a 27 − 1 (el exponente de 27 es 3, y 3 divide a 13 − 1), lo que implica que 13 también divide a 729 − 1 (el exponente de 729 es 6 y es un múltiplo de 3).

El mismo Fermat dejó su teorema sin prueba. El primer matemático en encontrar una prueba fue Gottfried Wilhelm Leibniz, cuyos manuscritos indican que conocía la prueba antes de 1683. Leibniz desconocía el resultado de Fermat y descubrió el teorema de forma independiente [6] . Sin embargo, el trabajo de Leibniz no fue publicado, y la prueba fue publicada por Euler en 1736 en Theorematum Quorundam ad Numeros Primos Spectantium Demonstrio [7] . En 1806, el matemático escocés James Ivory publicó una prueba basada en el hecho de que si pasa por el sistema completo de residuos módulo , entonces para cualquier producto no múltiple también pasa por el sistema completo de residuos módulo esta idea es la base de las pruebas modernas [8] . $X$ $pags$ $a,$ $pags,$ $hacha$ ${\ estilo de visualización p;}$

El número se llama privado de Fermat . El matemático ruso D. A. Grave sugirió que el cociente de Fermat nunca es divisible por Para números primos que no excedan de 1000, esto es cierto, pero pronto se descubrió un contraejemplo: porque el cociente de Fermat es divisible por 1093 [9] . ${\frac{a^{p-1}-1}{p))$ $pags.$ ${\ estilo de visualización p = 1093, a = 2}$

Redacción alternativa

La siguiente formulación se distingue por la ausencia del requisito de que el número no sea divisible por : $a$ $pags$

Si es un número primo y es cualquier número entero , entonces es comparable a módulo , es decir, . $pags$ $a$ $un ^ {p}$ $a$ $pags$ $a^{p}\equiv a{\pmod {p}}$

Por ejemplo, si , entonces y . $a=7;p=5$ $7^{5}=16807=5\cdot 3361+2,$ $7=5\cpunto 1+2.$

Es fácil mostrar que esta formulación se reduce a la original. Entonces, si es divisible por , entonces y , es decir . Si no es divisible por , entonces la expresión es equivalente a la expresión [2] . $a$ $pags$ $a\equiv 0{\pmod {p}}$ $a^{p}\equiv 0{\pmod {p}}$ $a^{p}\equiv a{\pmod {p}}$ $a$ $pags$ $a^{p}\equiv a{\pmod {p}}$ $a^{p-1}\equiv 1{\pmod {p}}$

Tanto la formulación principal como la alternativa se pueden usar para probar si un número dado es primo (ver más abajo ), pero la formulación principal es más sólida en el sentido de que rechaza más números compuestos . Ejemplo: Comprobemos si es un número primo. Sea B obtenido en una formulación alternativa , y esto es comparable a 4 mod 6. Es decir, no se rechaza el número 6, no se refuta su simplicidad. Si volvemos al teorema original: , entonces , y esto no es comparable con 1 mod 6, como debería ser si p es un número primo. Entonces, la formulación básica es más eficiente para eliminar números compuestos. $6$ ${\ estilo de visualización a = 4.}$ $4^{6}=4096=682\times 6+4$ $a^{p-1}\equiv 1{\pmod {p))$ $4^{6-1}=4^{5}=1024=170\times 6+4$

Evidencia

Demostración del teorema propuesto por Leibniz

Considere un polinomio homogéneo de grado p con n variables:

S(x,y,z,\puntos,w)=(x+y+z+\puntos +w)^{p}-(x^{p}+y^{p}+z^{p}+\ puntos+w^{p}).

Abriendo los paréntesis, obtenemos el coeficiente en el monomio (donde al menos dos de las potencias no son iguales a cero, y la suma de todas las potencias es igual a p ) se llama coeficiente multinomial y se calcula mediante la fórmula $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ $\alfa,\beta,\gamma\ldots\nu$

M={\frac {p!}{\alpha !\beta !\gamma !\dots \nu !}}).

Dado que las potencias son menores que eso, el denominador del coeficiente multinomial no contiene factores que puedan cancelarse, por lo que todos los coeficientes del polinomio son múltiplos , por lo que se cumple la siguiente identidad: $\alfa,\beta,\gamma...$ $pags,$ $pags,$ $S$ $pags.$

(x+y+z+\puntos +w)^{p}-(x^{p}+y^{p}+z^{p}+\puntos +w^{p})=pH(x,y ,z,\puntos,w),

donde es un polinomio con coeficientes enteros positivos. $H(x,y,z,...,w)$

Sea ahora en esta identidad entonces (aquí n es el número de variables en la expresión polinomial original), por lo tanto, es un múltiplo de . Si no es divisible por un número primo, entonces [10] es divisible por él . $x=y=...=w=1,H(1,1,1,...,1)=N,$ $n^{p}-n=Np$ $n(n^{p-1}-1)$ $pags$ $norte$ $pags,$ $n^{{p-1}}-1$

Prueba por inducción

Probemos que para cualquier primo p y entero no negativo a , a p − a es divisible por p . Probamos por inducción sobre un .

Base. Para a = 0 , a p − a = 0 y es divisible por p .

Transición. Sea verdadera la proposición para a = k . Probémoslo para a = k + 1 .

a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \elegir l}k^{l}-k-1=k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \elegir l}

Pero k p − k es divisible por p por la hipótesis de inducción. El resto de los términos contienen el factor . Pues , el numerador de esta fracción es divisible por p , y el denominador es coprimo de p , por lo tanto, es divisible por p . Dado que todos los términos individuales son divisibles por p , la suma total también es divisible por p . ${p \elegir l}={p! \sobre l!(pl)!}$ $1\leqslant l\leqslant p-1$ ${p \ elegir l}$ $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \elegir l}$

Para a negativa y p impar , el teorema es fácil de probar sustituyendo b = − a . Para a negativo y p = 2 , la verdad del teorema se sigue de a 2 − a = a ( a − 1) [11] .

Demostración usando la teoría de grupos

Una de las demostraciones más sencillas del Pequeño Teorema de Fermat se basa en un corolario del teorema de Lagrange de la teoría de grupos , que establece que el orden de un elemento de un grupo finito divide el orden del grupo.

Recuerda que el orden de un grupo finito es el número de sus elementos, y el orden de un elemento es el menor exponente natural de su grado igual al elemento unidad del grupo . $GRAMO$ $g\in g$ $mi$ $GRAMO$

Sea un grupo finito de orden . Dado que el orden de los elementos se divide , se sigue que . $GRAMO$ $norte$ $g\in g$ $norte$ $g^{n}=e$

Considere el campo de los residuos módulo . La deducción de un número entero se denotará por . Los elementos distintos de cero del campo forman un grupo con respecto a la multiplicación. $\mathbb {Z} _{p}$ $pags$ $a$ $a$ $\mathbb {Z} _{p}$

El orden de este grupo es obviamente . Su único elemento es . Se deduce que para cada número que no es divisible por , pero esto solo significa comparación [1] $p-1$ $una$ $a$ $pags$ $a^{{p-1}}=1$ $a^{p-1}\equiv 1{\pmod {p}}$

Prueba usando aritmética modular

Lema. Para cualquier número primo y un entero que no sea un múltiplo de , el producto de y los números cuando se dividen por el resto dan los mismos números , posiblemente escritos en algún orden diferente. $pags$ $k$ $pags$ $k$ $1,2,3,\ldots,p-1$ $pags$ $1,2,3,\ldots,p-1,$

Prueba del lema

El producto y cualquiera de los números no es múltiplo de , por lo tanto, el resto no puede ser . Todos los restos son diferentes. Probemos la última afirmación por contradicción. Sea at y dos productos y dé al dividir por residuos idénticos, entonces la diferencia es un múltiplo de , lo cual es imposible, ya que no es un múltiplo de . En total, hay diferentes residuos distintos de cero de la división por . $k$ $1,2,3,\ldots,p-1$ $pags$ ${\ estilo de visualización 0}$ $a,b\in \{1,2,3,\ldots,p-1\}$ ${\ estilo de visualización a \ neq b}$ $Alaska$ $bk$ $pags$ $ak-bk=(ab)k$ $pags$ $abdominales$ $pags$ $p-1$ $pags$

Ya que, según el lema anterior, los residuos de dividir los números a , 2 a , 3 a , ..., ( p − 1) a son, hasta una permutación del número 1, 2, 3, ... , pags − 1 , entonces . Desde aquí ¡ La última relación se puede reducir a ( p − 1)! , dado que todos los factores son números coprimos con base p , como resultado obtenemos el enunciado requerido [12] . $a\cdot 2a\cdot 3a\ldots (p-1)a\equiv 1\cdot 2\cdot 3\ldots (p-1){\pmod {p))$ $a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p))$ $a^{p-1}\equiv 1{\pmod {p}}$

Consecuencias y generalizaciones

Si es un número primo, entonces la igualdad [13] es verdadera en el campo . $pags$ $\mathbb {Z} _{p}$ $a^{-1}=a^{p-2}$
Si es un número primo distinto de 2 y 5, entonces el número cuya notación decimal contiene solo dígitos es divisible por . De ello se deduce que para cualquier número entero que no sea divisible por 2 ni por 5, puede elegir un número que consta solo de nueves, que es divisible por . Este hecho se utiliza en la teoría de signos de divisibilidad y fracciones periódicas [14] . $pags$ $10^{p-1}-1$ $9$ $pags$ $norte$ $norte$
El pequeño teorema de Fermat te permite encontrar divisores primos de números de la forma y [15] . $a^{4}+a^{3}+a^{2}+a+1$ $a^{2^{n}}+1$
Una generalización del pequeño teorema de Fermat a números algebraicos es un teorema formulado por Schönemann en 1839: sean las raíces de un polinomio normalizado de grado d y p un número primo. Entonces [16] . $a_{1},\puntos,a_{d}$ $f\en \mathbb {Z} [x]$ $a_{1}^{p}+a_{2}^{p}+\puntos +a_{d}^{p}\equiv a_{1}+\puntos +a_{d}{\pmod {p))$
El pequeño teorema de Fermat implica el teorema de Wilson : un número natural es primo si y solo si es divisible por p . $pag>1$ $(p-1)!+1$

Prueba del teorema de Wilson

El teorema de Lagrange en teoría de números establece que si un polinomio de grado es divisible por un número primo por más de un módulo incomparable (es decir, tiene diferentes residuos cuando se divide por ) valores de la variable , entonces es divisible por en cualquier valor . $norte$ $pags$ $norte$ $pags$ $pags$ $X$ $pags$ $X$

Considere el polinomio

G(x)=(x-1)(x-2)(x-3)...(x-(p-1))-(x^{p-1}-1),

donde es un número primo.

pags

Entonces encontramos:

G(1)=0,G(2)=1-2^{p-1},G(3)=1-3^{p-1},...,G(p-1)=1- (p-1)^{p-1}.

En virtud del pequeño teorema de Fermat, todos estos números son divisibles por un número primo , por lo que la comparación tiene soluciones incongruentes. Por otro lado, el grado de un polinomio es solo de esto se sigue que el polinomio es divisible por para todos los valores y en particular para $pags$ $G(x)\equiv 0{\pmod {p}}$ $p-1$ $p-2;$ $g(x)$ $pags$ $X,$ $x=0.$

Medio $G(0)=[(p-1)!+1]\equiv 0{\pmod {p}}.$

Y si además de esto demostramos que para todos los naturales no simples , excepto , , entonces obtenemos la demostración del teorema. [17] $norte$ $n=4$ $(n-1)!\equiv 0{\pmod {n}}$

Aplicaciones

Pseudoprimos de Fermat y pruebas de primalidad

El pequeño teorema de Fermat se puede usar para probar si un número es primo: si no es divisible por , entonces es un número compuesto . Sin embargo, el recíproco del pequeño teorema de Fermat es generalmente incorrecto: si y son números coprimos y son divisibles por , entonces el número puede ser tanto primo como compuesto. En el caso de que sea compuesto, se le llama pseudosimple de Fermat a la base . $(a^{p}-a)$ $pags$ $pags$ $a$ $pags$ $a^{p-1} - 1$ $pags$ $pags$ $pags$ $a$

Por ejemplo, la hipótesis china establece que es un número primo si y solo si [18] . Aquí hay una afirmación directa de que si es primo, entonces , es un caso especial del pequeño teorema de Fermat. La afirmación inversa de que si , entonces es simple, es un caso especial de la inversión del pequeño teorema de Fermat. Esta conversión es falsa: Sarrus descubrió en 1820 que un número es divisible por porque es divisible por . Sin embargo, es un número compuesto : . Por lo tanto, es un número pseudoprimo en base 2 [19] . $pags$ $2^{p}\equiv 2{\pmod {p}}$ $pags$ $2^{p}\equiv 2{\pmod {p}}$ $2^{p}\equiv 2{\pmod {p}}$ $pags$ ${\ estilo de visualización N = 2^{341-1}-1}$ $341$ $norte$ $2^{10}-1=3\cdot 341$ $341$ $341=11\cdot 31$ $341$

En el caso general, el inverso del Pequeño Teorema de Fermat también falla. Un contraejemplo en el caso general son los números de Carmichael : estos son números que son pseudoprimos en base para todos los coprimos a . El más pequeño de los números de Carmichael es 561. $pags$ $a$ $a$ $pags$

Debido a que el inverso del pequeño teorema de Fermat es incorrecto, el cumplimiento de su condición no garantiza que sea un número primo . Sin embargo, el pequeño teorema de Fermat subyace a la prueba de primalidad de Fermat [20] . La prueba de Fermat es una prueba de primalidad probabilística: si el teorema no es verdadero, entonces el número es exactamente compuesto, y si lo es, entonces el número es primo con cierta probabilidad . Entre otros métodos probabilísticos, se pueden señalar: la prueba de Solovay-Strassen y la prueba de Miller-Rabin , esta última en cierta medida se basa en el pequeño teorema de Fermat [21] . También existe un algoritmo determinista : la prueba de Agrawal-Kayala-Saksen . $pags$

Además, las siguientes dos afirmaciones son verdaderas. Si un par satisface la comparación , entonces el par de números también la satisface. Para cualquier número primo y cualquiera tal que , el valor es un pseudoprimo de Fermat a la base [22] . ${\ estilo de visualización (2, n)}$ $a^{n-1}\equiv 1{\pmod {n}}$ $(2.2^{n}-1)$ $norte$ $a>2$ $(a^{2}-1,n)=1$ ${\ fracción {a^{2n}-1}{a^{2}-1}}$ $a$

Algoritmo RSA

El pequeño teorema de Fermat también se utiliza para probar la corrección del algoritmo de cifrado RSA [2] .

Véase también

Notas

↑ 1 2 Vinberg, 2008 , pág. 43.
↑ 1 2 3 Sagalovich, 2014 , pág. 34.
↑ Encyclopedia of Elementary Mathematics, Libro 1, Aritmética, Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya., 1961.— P. 280
↑ Z. I. Borevich, I. R. Shafarevich. Teoría de los números. — M .: Nauka, 1972. — 175 p.
↑ Gracian E. Números primos. Largo camino al infinito. - De Agostini, 2014. - T. 3. - S. 45. - 148 p. — (Mundo de las Matemáticas). - ISBN 978-5-9774-0637-6 .
↑ Danzig, T. Números: el lenguaje de la ciencia, 2008 , p. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Teoría de números a través de la investigación Archivado el 16 de septiembre de 2012 en Wayback Machine . - 2006. - págs. 62-63.
↑ John J. O'Connor y Edmund F. Robertson . Sir James Ivory es una biografía del archivo MacTutor .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Detrás de las páginas de un libro de texto de matemáticas: Aritmética. Álgebra. geometría _ - M. : Educación, 1996. - S. 30 . — 320 s. — ISBN 5-09-006575-6 .
↑ Danzig, T. Números: el lenguaje de la ciencia, 2008 , p. 231-234.
↑ Vinberg, 2008 , pág. 44.
↑ QUANTUM, 2000, No. 1, Senderov V, Pequeño teorema de Spivak A. Fermat.
↑ Akritas A. Fundamentos de álgebra informática con aplicaciones, página 83.
↑ Danzig, T. Números: el lenguaje de la ciencia, 2008 , p. 232-234.
↑ QUANTUM, 2000, No. 3, Senderov V, El pequeño teorema de Spivak A Fermat
↑ Vinberg, 2008 , pág. 49.
↑ Danzig, T. Los números son el lenguaje de la ciencia, 2008 , p. 234-238.
↑ Ribenboim, P. (1996), The New Book of Prime Number Records, Nueva York: Springer-Verlag, págs. 103-105, ISBN 0-387-94457-5 .
↑ Weisstein EW Fermat Pseudoprime .. - 2005 ..
↑ Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Seguridad de la información: un libro de texto. - M.: MIPT, 2011. - S. 236-237. — 262 págs. Con. — ISBN 978-5-7417-0377-9 .
↑ Prueba de primalidad de Williams HC en una computadora // Ars Combin. - 1978. - vol. T. 5 , núm. No. 12 _ — pág. 127-185 .
↑ Shitov Yu. A. Métodos numéricos en criptografía.

Literatura

Aleksandrov P. S., Markushevich A. I., Khinchin A. Ya. Enciclopedia de matemáticas elementales. Volumen I: Aritmética. — 1951.
Borevich Z. I., Shafarevich I. R. Teoría de números . — M .: Nauka, 1972. — 510 p. Archivado el 8 de enero de 2011 en Wayback Machine .
El pequeño teorema de Vinberg EB Fermat y sus generalizaciones // Matem. iluminación - M. : Editorial del MTSNMO , 2008. - T. 12. - S. 43-53.
Gindikin S. G. "Pequeño teorema de Fermat" . - Kvant , 1972. - Nº 10 . (enlace no disponible)
Danzig, T. Los números son el lenguaje de la ciencia . - M .: Technosfera, 2008. - ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Problemas algorítmicos de teoría de números . - 1997. - Edición. 2 , nº tercera serie .
Sagalovich Yu. L. Introducción a los códigos algebraicos - 3ª ed., revisada. y adicional - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Senderov V, el pequeño teorema de Spivak A. Fermat // Kvant. - 2000. - Nº 1 .
Senderov V, el pequeño teorema de Spivak A. Fermat // Kvant. - 2000. - Nº 3 .