El pequeño teorema de Fermat

En teoría de números , 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 aritmética modular , esto se expresa como

a^{p}\equiv a{\pmod {p}}.

Por ejemplo, si $a = 2$ y $p = 7$ , entonces $27 = 128$ y $128 - 2 = 126 = 7 \times 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 ]}

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

Por ejemplo, si $a = 2$ y $p = 7$ , entonces $26 = 64$ y $64 - 1 = 63 = 7 \times 9$ es, por 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 estableció en 1640. Se le llama "pequeño teorema" para distinguirlo del último teorema de Fermat . ^[3]

Historia

Pierre de Fermat expuso 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 equivale a la siguiente: ^[3]

Si $p$ es 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 los expositores múltiples de la exposición del estreno que satisfacen también a la pregunta. $-1$ $-1$

Esto puede traducirse, con explicaciones y fórmulas agregadas entre paréntesis para una mejor comprensión, como:

Todo número primo [ $p ] divide necesariamente una de las potencias menos uno de cualquier$ progresión [geométrica] [ $a, a 2, a 3, \dots$ ] [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$ ]. Después de haber encontrado la primera potencia [ $t$ ] que satisface la pregunta, todos aquellos cuyos exponentes sean 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 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 cierta para todas las series [ sic ] y para todos los números primos; les enviaría una demostración de ello, 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 las Actas de la Academia de San Petersburgo, ^[6]^[7] pero Leibniz había dado prácticamente la misma prueba en un manuscrito inédito. desde algún momento antes de 1683. ^[3]

El término "pequeño teorema de Fermat" probablemente se utilizó por primera vez en forma impresa en 1913 en Zahlentheorie por 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.

(Hay un teorema fundamental que se cumple en cada grupo finito, generalmente llamado pequeño teorema de Fermat porque Fermat fue el primero en demostrar una parte muy especial del mismo).

Un uso temprano en inglés ocurre en Modern Higher Algebra (1937) de AA Albert , que se refiere al "llamado 'pequeño' teorema de Fermat" en la página 206. ^[9]

Más historia

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

Pruebas

Se conocen varias demostraciones del pequeño teorema de Fermat. Con frecuencia se demuestra como 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 número entero $coprimo$ de $n$ , se tiene

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

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

x\equiv y{\pmod {\varphi (n)}}\quad {\text{implica}}\quad a^{x}\equiv a^{y}{\pmod {n}},

x

y

x

=

y

+

kφ

(

n

)

k

x\equiv y{\pmod {\varphi (n)}}

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 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

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

x

y

e

n

φ (n)

^[11]algoritmo euclidiano extendido inverso modular

e

φ (n)

f

ef\equiv 1{\pmod {\varphi (n)}}.

x\equiv 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$ a partir de $n$ y $e$ es tan difícil como calcular $φ (n)$ (esto no ha sido 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 a la inversa, los factores $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 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 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 número entero $a$ tal que

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

q que

p - 1

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

p

Este teorema forma la base de la prueba de primalidad de Lucas , una prueba de primalidad importante , y del certificado de primalidad de Pratt .

pseudoprimos

Si $a$ y $p$ son números coprimos tales que $a p -1 - 1$ es divisible por $p$ , entonces $p$ no tiene por qué ser primo. Si no es así, entonces $p$ se llama pseudoprimo (Fermat) para la base $a$ . El primer pseudoprimo de 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 $coprimo$ de $p$ se llama número de Carmichael . Alternativamente, cualquier número $p$ que satisfaga la igualdad

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

Prueba de primalidad de Miller-Rabin

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 de $p$ , o $a d \equiv 1 (mod p)$ o existe $r$ tal que $0 \leq r < s$ y $a 2 r d \equiv -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 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 la misma razón. Es por eso que normalmente se elige una a aleatoria $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, 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 eleva al cuadrado repetidamente módulo $p$ hasta obtener −1 o elevar 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 fuerte y probable con base a ; es decir, puede ser primo o no. Si $p$ es compuesto, la probabilidad de que la prueba lo declare un primo fuerte probable de todos modos 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, por lo tanto, puede reducirse tanto 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 ser tan baja como se desee. La prueba es muy sencilla de implementar y computacionalmente más eficiente que todas las pruebas deterministas conocidas. Por tanto, generalmente se utiliza antes de iniciar 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

^ Largo 1972, págs. 87–88.
^ Pettofrezzo y Byrkit 1970, págs. 110-111.
^ abc Burton 2011, pag. 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, pag. 295 para la traducción al inglés
^ Euler, Leonhard (1736). "Theorematum quorundam ad numeros primos spectantium demonstratio" [Demostración de ciertos teoremas relativos a los números primos]. Commentarii Academiae Scientiarum Imperialis Petropolitanae (Memorias de la Academia Imperial de Ciencias de San Petersburgo) (en latín). 8 : 141-146.
^ Mineral 1988, pag. 273
^ Hensel, Kurt (1913). Zahlentheorie [ Teoría de números ] (en alemán). Berlín y Leipzig, Alemania: GJ Göschen. pag. 103.
^ Alberto 2015, pag. 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
^ Si $y$ no es coprimo con $n$ , el teorema de Euler no funciona, pero este caso es lo suficientemente raro como para no ser considerado. De hecho, si ocurriera por casualidad, esto proporcionaría una factorización fácil de $n$ y, por lo tanto, rompería la instancia considerada de RSA.
^ Sloane, Nueva Jersey (ed.). "Secuencia A128311 (resto de la división de 2n−1−1 por n.)". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
^ Sarrus, Federico (1819-1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Demostración de la falsedad del teorema expuesto 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 la unidad módulo a primo)". Pruebas de primalidad para principiantes . Sociedad Matemática Estadounidense. 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 / Introducción (7ª ed.), McGraw-Hill, ISBN 978-0-07-338315-6
Long, Calvin T. (1972), Introducción elemental a la teoría de números (2ª 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
János Bolyai y los pseudoprimos (en húngaro)
El pequeño teorema de Fermat al cortar el nudo
Función de Euler y teorema del corte del nudo
El pequeño teorema de Fermat y la prueba de Sophie
"El pequeño teorema de Fermat", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
Weisstein, Eric W. "El pequeño teorema de Fermat". MundoMatemático .
Weisstein, Eric W. "El pequeño teorema inverso de Fermat". MundoMatemático .