Pequeno 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

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

Por exemplo, se a = 2 e p = 7, entón 2⁷ = 128 e 128 − 2 = 126 = 7 × 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]}

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

Por exemplo, se a = 2 e p = 7, entón 2⁶ = 64 e 64 − 1 = 63 = 7 × 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]

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 ${\displaystyle -1}$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ${\displaystyle -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]

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 ${\displaystyle \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:

${\displaystyle {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 ${\displaystyle \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:

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

• Agrupando factores e reordenando:

${\displaystyle (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 ${\displaystyle a^{p}-a\equiv 0{\pmod {p}}}$.

Q.E.D

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

${\displaystyle 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

${\displaystyle 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

${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$, entón x = y + kφ(n) para algún número enteiro k,

daquela temos

${\displaystyle 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.

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

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

e para todos os primos q que dividen p − 1 temos que

${\displaystyle 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.

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

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

é un número primo ou de Carmichael.

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^sd con s > 0 e d impar > 0, entón para cada a coprimo con p, daquela temos que ou a^d ≡ 1 (mod p) ou existe r tal que 0 ≤ r < s e a^2rd ≡ −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 ≡ 1 (mod p) cúmprese trivialmente para a ≡ 1 (mod p), porque a relación de congruencia é compatíbel coa exponenciación . E a^d = a^20d ≡ −1 (mod p) cúmprese trivialmente para a ≡ −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^sd 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 ≠ 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.

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

• Teorema de Fermat.
• RSA.

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