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 
:a^p \equiv a \pmod p.

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 :  
:a^{p-1} \equiv 1 \pmod p.

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 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 \textstyle{p \choose n} é divisíbel por *p*, para todos os *n*, de xeito que 1≤ *n*{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 \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:

: (n+1)^p=\sum_{k=0}^{p}{p \choose k}n^{p-k}

* Agrupando factores e reordenando:

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

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

:a^{\varphi (n)} \equiv 1 \pmod n,

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 
:x \equiv y \pmod{\varphi(n)}\quad\text{implica}\quad a^x \equiv a^y \pmod n,  
para calquera número enteiro  e . Isto despréndese do teorema de Euler, xa que, se 
: x \equiv y \pmod{\varphi(n)}, entón  para algún número enteiro , 
daquela temos 
:a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.

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 
:  a^{p-1}\equiv 1\pmod p  
e para todos os primos  que dividen  temos que 
: a^{(p-1)/q}\not\equiv 1\pmod p,  
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&nbsp;×&nbsp;31.

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 
:\gcd\left(p, \sum_{a=1}^{p-1} a^{p-1}\right)=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  é 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