Pequeno teorema de Fermat

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

$a^p\equiv a(\mathrm{mod}p).$

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

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

$a^{p-1}\equiv 1(\mathrm{mod}p).$

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

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

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 Modelo:Mvar é primo e Modelo:Mvar é calquera número enteiro non divisíbel por Modelo:Mvar, daquela Modelo:Math é divisíbel por Modelo:Mvar.

A declaración orixinal de Fermat era

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,

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 $(\genfrac{}{}{0ex}{}{p}{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:

$(\genfrac{}{}{0ex}{}{p}{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 $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(\genfrac{}{}{0ex}{}{p}{k})n^{p-k}$

• Agrupando factores e reordenando:

$(n+1{)}^p-(n+1)=n^p-n+\sum _{k=1}^{p-1}(\genfrac{}{}{0ex}{}{p}{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(\mathrm{mod}p)$.

Q.E.D

Xeneralizacións

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

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

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

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

$x\equiv y(\mathrm{mod}\phi (n))\text{implica}{a}^x\equiv a^y(\mathrm{mod}n),$

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

$x\equiv y(\mathrm{mod}\phi (n))$, entón Modelo:Math para algún número enteiro Modelo:Mvar,

daquela temos

$a^x=a^{y+\phi (n)k}=a^y(a^{\phi (n)}{)}^k\equiv a^y{1}^k\equiv a^y(\mathrm{mod}n).$

Se Modelo:Mvar é 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 Modelo:Mvar.

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 Modelo:Mvar tal que

$a^{p-1}\equiv 1(\mathrm{mod}p)$

e para todos os primos Modelo:Mvar que dividen Modelo:Math temos que

$a^{(p-1)/q}\equiv ̸1(\mathrm{mod}p),$

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

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

$\gcd (p,\sum _{a=1}^{p-1}{a}^{p-1})=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:

Se Modelo:Mvar é un primo impar e Modelo:Math con Modelo:Math e Modelo:Mvar impar > 0, entón para cada Modelo:Mvar coprimo con Modelo:Mvar, daquela temos que ou Modelo:Math ou existe Modelo:Mvar tal que Modelo:Math e Modelo:Math .

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

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

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

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.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

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

Modelo:Control de autoridades