El pequeño teorema de Fermat

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Para cada p primitiva, la diferencia entre cualquier entero y su poder p-th es un múltiplo de p

El pequeño teorema de Fermat dice que si p es un número primo, entonces para cualquier entero a, el número ${displaystyle a^{p}-a}$ es un número entero de p. En la notación de aritmética modular, esto se expresa como

a^p equiv a pmod p.

Por ejemplo, si $a$ = 2 y $p$ = 7, luego 2⁷ = 128, y 128 − 2 = 126 = 7 × 18 es un número entero múltiplo de 7.

Si $a$ no es divisible por $p$ , es decir, si $a$ es coprimo con $p$ , 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:

a^{p-1} equiv 1 pmod p.

Por ejemplo, si $a$ = 2 y $p$ = 7, luego 2⁶ = 64, y 64 − 1 = 63 = 7 × 9 es, por lo tanto, 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 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.

Historia

Pierre de Fermat

Pierre de Fermat planteó 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:

Si $p$ es un primo $a$ es cualquier 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 $-1$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné $-1$ ; 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 añadidas entre paréntesis para facilitar la comprensión, como:

Cada número primo [ $p$ ] divide necesariamente uno de los poderes menos uno de cualquier progresión [geométrica] [ $a, a 2, a 3,...$ [eso es, existe $t$ tales que $p$ divideciones $a t - 1$ ], y el exponente de este poder [ $t$ # divide el primero menos uno [divides $p - 1$ ]. Después de haber encontrado el primer poder [ $t$ ] que satisface la pregunta, todos aquellos cuyos exponentes son múltiplos del exponente de la primera satisfacen igualmente la pregunta [es decir, todos los múltiplos de la primera $t$ tienen la misma propiedad].

Fermat no consideró el caso donde $a$ es múltiplo de $p$ ni probar su aseveración, solo afirmando:

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 propuesta es generalmente verdadera para toda la serie [sic] y para todos los números primos; Yo te enviaría una demostración de ello, si no temía seguir adelante durante demasiado tiempo.)

Euler proporcionó la primera prueba publicada en 1736, en un artículo titulado "Theorematum Quorundam ad Numeros Primos Spectantium Demonstrio" en las Proceedings de la Academia de San Petersburgo, pero Leibniz había dado prácticamente la misma prueba en un manuscrito inédito de algún tiempo antes de 1683.

El término "pequeño teorema de Fermat" probablemente se utilizó 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 en cada grupo finito, generalmente llamado teorema pequeño de Fermat porque Fermat fue el primero en probar una parte muy especial de él.)

Un uso temprano en inglés ocurre en A.A. Albert's Modern Higher Algebra (1937), que se refiere a "los llamados 'pequeños' Teorema de Fermat" en la página 206.

Más historia

Algunos matemáticos formularon de forma independiente la hipótesis relacionada (a veces llamada incorrectamente la hipótesis china) de que $2 p \equiv 2 (mod p)$ si y solo si $p$ es primo. De hecho, el "si" parte es cierta, y es un caso especial del pequeño teorema de Fermat. Sin embargo, el "solo si" parte es falsa: por ejemplo, $2341 \equiv 2 (mod 341)$ , pero 341 = 11 × 31 es un pseudoprimo. Vea abajo.

Pruebas

Se conocen varias demostraciones 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 $a$ coprimo a $n$ , uno tiene

{displaystyle a^{varphi (n)}equiv 1{pmod {n}},}

donde $φ (n)$ denota la función totient de Euler (que cuenta los números enteros del 1 al $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 coprincipal con $n$ entonces

{displaystyle xequiv y{pmod {varphi (n)}}quad {text{implies}}quad a^{x}equiv a^{y}{pmod {n}},}

para cualquier entero $x$ y $Sí.$ . Esto sigue del teorema de Euler, ya que, si $x equiv y pmod{varphi(n)}$ , entonces $x = Sí. + kφ () n)$ para algunos enteros $k$ , y uno tiene

{displaystyle a^{x}=a^{y+varphi (n)k}=a^{y}(a^{varphi (n)})^{k}equiv a^{y}1^{k}equiv a^{y}{pmod {n}}.}

Si $n$ es primo, esto también es un corolario del pequeño teorema de Fermat. Esto se usa ampliamente en la aritmética modular, porque permite reducir la exponenciación modular con exponentes grandes a exponentes más pequeños que $n$ .

El teorema de Euler se usa con $n$ not prime en la criptografía de clave pública, específicamente en el criptosistema RSA, típicamente de la siguiente manera: si

{displaystyle y=x^{e}{pmod {n}},}

recuperación $x$ de los valores $Sí.$ , $e$ y $n$ es fácil si uno sabe $φ () n)$ . De hecho, el algoritmo ampliado de Euclidean permite calcular el inverso modular de $e$ modulo $φ () n)$ , ese es el entero $f$ tales que ${displaystyle efequiv 1{pmod {varphi (n)}}.}$ De ello se desprende que

{displaystyle xequiv x^{ef}equiv (x^{e})^{f}equiv y^{f}{pmod {n}}.}

Por otro lado, si $n = pq$ es el producto de dos números primos distintos, entonces φ(n) = (p − 1)(q − 1). En este caso, encontrar $f$ de $n$ y $e$ es tan difícil como calcular $φ (n)$ (esto no se ha probado, 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 por el contrario, 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: si un mensaje $x$ se cifra como $y = x e (mod n)$ , usando valores públicos de $n$ y $e$ , entonces, con el actual conocimiento, 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.

Conversar

El inverso del pequeño teorema de Fermat generalmente no es cierto, ya que falla para los números de Carmichael. Sin embargo, una forma ligeramente más fuerte del teorema es cierta y se conoce como el teorema de Lehmer. El teorema es el siguiente:

Si existe un entero $a$ tal que

a^{p-1}equiv 1pmod p

y para todos los primos $q$ dividiendo $p - 1$ uno tiene

{displaystyle a^{(p-1)/q}not equiv 1{pmod {p}},}

entonces $p$ es primo.

Este teorema constituye la base de la prueba de primalidad de Lucas, una importante prueba de primalidad y el certificado de primalidad de Pratt.

Pseudoprimos

Si $a$ y $p$ son números coprimos tales que $a p -1 - 1$ es divisible por $p$ , luego $p$ no necesita ser primo. Si no lo es, entonces $p$ se denomina (Fermat) pseudoprime para basar a. El primer pseudoprimo de base 2 fue encontrado en 1820 por Pierre Frédéric Sarrus: 341 = 11 × 31.

Un número $p$ que es un pseudoprimo de Fermat a base $a$ para cada número $a$ coprimos a $p$ se denomina número de Carmichael (por ejemplo, 561). Alternativamente, cualquier número $p$ que satisfaga la igualdad

{displaystyle gcd left(p,sum _{a=1}^{p-1}a^{p-1}right)=1}

es un número primo o de Carmichael.

Prueba de primalidad de Miller-Rabin

La prueba de primalidad de Miller-Rabin utiliza la siguiente extensión del pequeño teorema de Fermat:

Si $p$ es una prima rara y $p - 1 = 2 s d$ con $s œ 0$ y $d$ impares 0, entonces por cada $a$ coprime $p$ , o $a d (modelo) p)$ o existe $r$ tales que $0 \leq r . s$ y $a 2 r d (modelo) p)$ .

Este resultado puede deducirse del pequeño teorema de Fermat por el hecho de que, si $p$ es un primo impar, entonces los enteros módulo $p$ forman un campo finito, en el que 1 módulo $p$ tiene exactamente dos raíces cuadradas, 1 y −1 módulo $p$ .

Tenga en cuenta que $a d \equiv 1 (mod p)$ se cumple trivialmente para $a \equiv 1 (mod p)$ , porque la relación de congruencia es compatible con la exponenciación. Y $a d = a 20 d \equiv -1 (mod p)$ se cumple trivialmente para $a \equiv -1 (mod p)$ ya que $d$ es impar, por el Misma razón. Es por eso que normalmente se elige una $a$ aleatoria en el intervalo $1 < a < p - 1$ .

La prueba Miller-Rabin usa esta propiedad de la siguiente manera: dado un entero impar $p$ para el cual la primalidad debe ser probado, escriba $p - 1 = 2 s d$ con $s > 0$ y $d$ impar > 0, y elija un $a$ aleatorio tal que $1 < a < p - 1$ ; luego calcule $b = a d mod p; si b no es 1 ni -1, entonces cuadrelo repetidamente modulo p hasta que obtenga -1 o haya elevado al cuadrado s - 1 veces. Si b \neq 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 basar a, es decir, puede ser primo o no. Si p es compuesto, la probabilidad de que la prueba lo declare un primo probable fuerte de todos modos es como mucho 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 es compuesta como máximo 4 - k y, por lo tanto, puede hacerse tan bajo como se desee aumentando k .$

En resumen, la prueba prueba que un número es compuesto o afirma que es primo con una probabilidad de error que se puede elegir 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.

Contenido relacionado

Más resultados...