Pequeno teorema de Fermat

teorema sobre a primalidade dun número

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 apa é un múltiplo enteiro de p. Na notación de aritmética modular, isto exprésase como

Por exemplo, se a = 2 e p = 7, entón 27 = 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 ap − 1 − 1 é un múltiplo enteiro de p:[1] [2]

Por exemplo, se a = 2 e p = 7, entón 26 = 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]

Historia

editar
 
Pierre de Fermat

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   de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné  ; 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

editar

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   é divisíbel por p, para todos os n, de xeito que 1≤ n<p. Isto é así xa que o coeficiente binomial defínese como:

 

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  ; (p divide a n elevado a p menos n).
 
  • Agrupando factores e reordenando:
 
  • Por hipótese, asumíramos que np - 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  .

Q.E.D

Xeneralizacións

editar

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

 

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

 

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

 , entón x = y + (n) para algún número enteiro k,

daquela temos

 

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

editar

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

 

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

 

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

editar

Se a e p son números primos tal que ap−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

 

é un número primo ou de Carmichael.

Test de primalidade de Miller-Rabin

editar

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 = 2sd con s > 0 e d impar > 0, entón para cada a coprimo con p, daquela temos que ou ad ≡ 1 (mod p) ou existe r tal que 0 ≤ r < s e a2rd ≡ −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 ad ≡ 1 (mod p) cúmprese trivialmente para a ≡ 1 (mod p), porque a relación de congruencia é compatíbel coa exponenciación . E ad = a20d ≡ −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 = 2sd con s > 0 e d impar > 0 e escolla un a aleatorio tal que 1 < a < p − 1; entón calcule b = ad 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áximo14, 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 4k, 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.

  1. Long 1972.
  2. Pettofrezzo & Byrkit 1970.
  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 2n−1−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. 

Véxase tamén

editar

Bibliografía

editar

Outros artigos

editar

Ligazóns externas

editar