Pequeno teorema de Fermat

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

Por exemplo, se  e , entón  e  é un múltiplo enteiro de .

Se  non é divisíbel por , é dicir, se  é coprimo con , entón o pequeno teorema de Fermat é equivalente á afirmación de que  é un múltiplo enteiro de :. . 

Por exemplo, se  e , entón  e  é múltiplo de  .

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

 Historia 
dereita|miniatura| 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: .Se  é primo e  é calquera número enteiro non divisíbel por , daquela  é divisíbel por .A declaración orixinal de Fermat eraEuler 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,

 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  é 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).

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



 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 
O teorema de Euler é unha xeneralización do pequeno teorema de Fermat: para calquera módulo  e calquera número enteiro  coprimo con , temos

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

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

para calquera número enteiro  e . Isto despréndese do teorema de Euler, xa que, se 
 , entón  para algún número enteiro , 
daquela temos 

Se  é 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 .

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

e para todos os primos  que dividen  temos que 

entón  é 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  e  son números primos tal que  é divisíbel por , entón  non é obrigatoriamente primo. Se non o é, entón  chámase pseudoprimo (de Fermat) en base . O primeiro pseudoprimo en base 2 foi atopado en 1820 por Pierre Frédéric Sarrus: 341 = 11 × 31. Remainder upon division of 2n−1−1 by n.

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

é 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: Se  é un primo impar e  con  e  impar > 0, entón para cada  coprimo con , daquela temos que ou  ou existe  tal que  e  .Este resultado pódese deducir do pequeno teorema de Fermat polo feito de que, se  é un primo impar, entón os enteiros módulo  forman un corpo finito, no que 1 módulo  ten exactamente dúas raíces cadradas, 1 e −1 módulo  .

Teña en conta que  cúmprese trivialmente para , porque a relación de congruencia é compatíbel coa exponenciación . E  cúmprese trivialmente para  xa que  é impar, pola mesma razón. Por iso adoitase escoller unha  aleatoria no intervalo .

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

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 


 Véxase tamén 

 Bibliografía 







 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

Categoría:Teoremas
Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas