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