Pequeno teorema de Fermat

Para outras páxinas con títulos homónimos véxase: Teorema de Fermat.

En teoría de números, o pequeno teorema de Fermat afirma que se $p$ é un número primo, entón para calquera número enteiro $a$ , o número $a p - a$ é un múltiplo enteiro de $p$ . Na notación de aritmética modular, isto exprésase como

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

Por exemplo, se $a = 2$ e $p = 7$ , entón $27 = 128$ e $128 - 2 = 126 = 7 \times 18$ é un múltiplo enteiro de $7$ .

Se $a$ non é divisíbel por $p$ , é dicir, se $a$ é coprimo con $p$ , entón o pequeno teorema de Fermat é equivalente á afirmación de que $a p - 1 - 1$ é un múltiplo enteiro de $p$ :^[1] ^[2]

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

Por exemplo, se $a = 2$ e $p = 7$ , entón $26 = 64$ e $64 - 1 = 63 = 7 \times 9$ é múltiplo de $7$ .

O pequeno teorema de Fermat é a base para o test de primalidade de Fermat e é un dos resultados fundamentais da teoría de números elemental. O teorema recibe o nome de Pierre de Fermat, quen o enunciou en 1640. Chámase "pequeno teorema" para distinguilo do último teorema de Fermat.^[3]

Historia

Pierre de Fermat enunciou por primeira vez o teorema nunha carta do 18 de outubro de 1640 ao seu amigo e confidente Frénicle de Bessy. A súa formulación é equivalente á seguinte: ^[3]

Se $p$ é primo e $a$ é calquera número enteiro non divisíbel por $p$ , daquela $a p - 1 - 1$ é divisíbel por $p$ .

A declaración orixinal de Fermat era

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.

Euler proporcionou a primeira proba publicada en 1736, nun artigo titulado "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" (en galego: "Demostración de certos teoremas relativos aos números primos") nos Proceedings of the St. Petersburg Academy,^[4]^[5]

Probas

Coñécense varias demostracións do pequeno teorema de Fermat. Probábase con frecuencia como corolario do teorema de Euler.

Imos ver unha demostración na que podemos usar a propiedade de que se p é un número primo, entón o coeficiente binomial $\textstyle {p \choose n}$ é divisíbel por p, para todos os n, de xeito que 1≤ n<p. Isto é así xa que o coeficiente binomial defínese como:

{p \choose n}={\frac {p!}{(p-n)!\cdot n!}}

Onde p! = p·(p-1)·(p-2)·...·2·1. Xa que no denominador, os factoriais dos números implican números que son menores que o número primo p, estes non poden conter p nin dividir o número primo p do numerador, polo que o coeficiente é divisíbel por p.

Dito isto, a proba consta dos seguintes pasos:

Supoña que $\textstyle {p\mid n^{p}-n}$ ; (p divide a n elevado a p menos n).

Usamos o binomio de Newton para expandir a potencia (n + 1)^p:

(n+1)^{p}=\sum _{k=0}^{p}{p \choose k}n^{p-k}

Agrupando factores e reordenando:

(n+1)^{p}-(n+1)=n^{p}-n+\sum _{k=1}^{p-1}{p \choose k}n^{p-k}

Por hipótese, asumíramos que n^p - n é divisíbel por p, e como todos os termos da suma do lado dereito son divisíbeis por p, temos que p divide (n + 1)^p - (n + 1). (Sabemos que os coeficientes binomiais son números enteiros).

Por tanto sustituíndo n por calquera enteiro temos n +1 = a, e por tanto $a^{p}-a\equiv 0{\pmod {p}}$ .

Q.E.D

Xeneralizacións

O teorema de Euler é unha xeneralización do pequeno teorema de Fermat: para calquera módulo $n$ e calquera número enteiro $a$ coprimo con $n$ , temos

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

onde $φ (n)$ denota a función totiente de Euler (que conta os enteiros de 1 a $n$ que son coprimos con $n$ ). O pequeno teorema de Fermat é realmente un caso especial, porque se $n$ é un número primo, entón $φ (n) = n - 1$ .

Un corolario do teorema de Euler é: Para todo número enteiro positivo $n$ , se o enteiro $a$ é coprimo con $n$ , entón

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

para calquera número enteiro $x$ e $y$ . Isto despréndese do teorema de Euler, xa que, se

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

, entón

x = y + kφ (n)

para algún número enteiro

k

,

daquela temos

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

Se $n$ é primo, este tamén é un corolario do pequeno teorema de Fermat. Isto é moi usado na aritmética modular, porque permite reducir a exponenciación modular con expoñentes grandes a expoñentes menores que $n$ .

Recíproca do teorema

A recíproca do pequeno teorema de Fermat falla para os números de Carmichael. No entanto, unha variante lixeiramente máis débil do recíproco é o teorema de Lehmer:

Se existe un número enteiro $a$ tal que

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

e para todos os primos $q$ que dividen $p - 1$ temos que

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

entón $p$ é primo.

Este teorema constitúe a base para o test de primalidade de Lucas, un test de primalidade importante. Tamén é a base de certificado de primalidade de Pratt.

Pseudoprimos

Se $a$ e $p$ son números primos tal que $a p -1 - 1$ é divisíbel por $p$ , entón $p$ non é obrigatoriamente primo. Se non o é, entón $p$ chámase pseudoprimo (de Fermat) en base $a$ . O primeiro pseudoprimo en base 2 foi atopado en 1820 por Pierre Frédéric Sarrus: 341 = 11 × 31.^[6]^[7]

Un número $p$ que é un pseudoprimo de Fermat en base $a$ para cada número coprimo $a$ $p$ chámase número de Carmichael. Alternativamente, calquera número $p$ que satisfaga a igualdade

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

é un número primo ou de Carmichael.

Test de primalidade de Miller-Rabin

O test de primalidade de Miller-Rabin usa a seguinte extensión do pequeno teorema de Fermat:^[8]

Se $p$ é un primo impar e $p - 1 = 2 s d$ con $s > 0$ e $d$ impar > 0, entón para cada $a$ coprimo con $p$ , daquela temos que ou $a d \equiv 1 (mod p)$ ou existe $r$ tal que $0 \leq r < s$ e $a 2 r d \equiv -1 (mod p)$ .

Este resultado pódese deducir do pequeno teorema de Fermat polo feito de que, se $p$ é un primo impar, entón os enteiros módulo $p$ forman un corpo finito, no que 1 módulo $p$ ten exactamente dúas raíces cadradas, 1 e −1 módulo $p$ .

Teña en conta que $a d \equiv 1 (mod p)$ cúmprese trivialmente para $a \equiv 1 (mod p)$ , porque a relación de congruencia é compatíbel coa exponenciación . E $a d = a 20 d \equiv -1 (mod p)$ cúmprese trivialmente para $a \equiv -1 (mod p)$ xa que $d$ é impar, pola mesma razón. Por iso adoitase escoller unha $a$ aleatoria no intervalo $1 < a < p - 1$ .

A proba de Miller-Rabin usa esta propiedade do seguinte xeito: dado un enteiro impar $p$ para o cal se debe probar a primalidade, escriba $p - 1 = 2 s d$ con $s > 0$ e $d$ impar > 0 e escolla un $a$ aleatorio tal que $1 < a < p - 1$ ; entón calcule $b = a d mod p$ ; se $b$ non é 1 nin −1 eléve $b$ ao cadrado repetidamente módulo $p$ ata obter −1 ou ata que sexa elevado ao cadrado $s - 1$ veces. Se nese bucle non obremos $b \neq 1$ e −1, entón $p$ é un número composto e $a$ é unha testemuña de que $p$ é composto. En caso contrario, $p$ é un primo probábel forte en base a; é dicir, pode ser primo ou non. Se $p$ é composto, a probabilidade de que a proba o declare un primo probábel forte é como máximo¹⁄₄, nese caso $p$ é un pseudoprimo forte e $a$ é un mentireiro forte. Polo tanto, despois de $k$ probas aleatorias non concluíntes, a probabilidade de que $p$ sexa composto é como máximo 4^−k, polo que se pode facer tan baixa como se desexe aumentando $k$ .

En resumo, o test demostra que un número é composto ou afirma que é primo cunha probabilidade de erro que se pode escoller tan baixa como se desexe. A proba é moi sinxela de implementar e computacionalmente máis eficiente que todas as probas deterministas coñecidas. Polo tanto, úsase xeralmente como primeiro intento antes de comezar unha proba de primalidade.

Notas

↑ Long 1972.
↑ Pettofrezzo & Byrkit 1970.
↑ ^3,0 ^3,1 Burton 2011.
↑ Euler, Leonhard (1736). "Theorematum quorundam ad numeros primos spectantium demonstratio" [Proof of certain theorems relating to prime numbers]. Commentarii Academiae Scientiarum Imperialis Petropolitanae (Memoirs of the Imperial Academy of Sciences in St. Petersburg) (en Latin) 8: 141–146.
↑ Ore 1988, p. 273
↑ (secuencia A128311 na OEIS) Remainder upon division of 2ⁿ⁻¹−1 by n.
↑ Sarrus, Frédéric (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Demonstration of the falsity of the theorem stated on page 320 of the 9th volume of this collection]. Annales de Mathématiques Pures et Appliquées (en francés) 10: 184–187.
↑ Rempe-Gillen, Lasse; Waldecker, Rebecca (2013-12-11). "4.5.1. Lemma (Roots of unity modulo a prime)". Primality Testing for Beginners. American Mathematical Soc. ISBN 9780821898833.

Véxase tamén

Bibliografía

Albert, A. Adrian (2015) [1938]. Modern higher algebra. Cambridge University Press. ISBN 978-1-107-54462-8.
Burton, David M. (2011). The History of Mathematics / An Introduction (7th ed.). McGraw-Hill. ISBN 978-0-07-338315-6.
Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950.
Mahoney, Michael Sean (1994). The Mathematical Career of Pierre de Fermat, 1601–1665 (2nd ed.). Princeton University Press. ISBN 978-0-691-03666-3.
Ore, Oystein (1988) [1948]. Number Theory and Its History. Dover. ISBN 978-0-486-65620-5.
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.

Outros artigos

Teorema de Fermat.
RSA.

Ligazóns externas

Fermat's Little Theorem at cut-the-knot
Euler Function and Theorem at cut-the-knot
Fermat's Little Theorem and Sophie's Proof

[1] Long 1972.

[2] Pettofrezzo & Byrkit 1970.

[Burton-3] 3,0 ^3,1 Burton 2011.

[4] Euler, Leonhard (1736). "Theorematum quorundam ad numeros primos spectantium demonstratio" [Proof of certain theorems relating to prime numbers]. Commentarii Academiae Scientiarum Imperialis Petropolitanae (Memoirs of the Imperial Academy of Sciences in St. Petersburg) (en Latin) 8: 141–146.

[5] Ore 1988, p. 273

[6] (secuencia A128311 na OEIS) Remainder upon division of 2ⁿ⁻¹−1 by n.

[7] Sarrus, Frédéric (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Demonstration of the falsity of the theorem stated on page 320 of the 9th volume of this collection]. Annales de Mathématiques Pures et Appliquées (en francés) 10: 184–187.

[8] Rempe-Gillen, Lasse; Waldecker, Rebecca (2013-12-11). "4.5.1. Lemma (Roots of unity modulo a prime)". Primality Testing for Beginners. American Mathematical Soc. ISBN 9780821898833.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]