Demonstração do Pequeno Teorema de Fermat  

Pequeno Teorema de Fermat

 Se p é primo então, para todo inteiro a

  $a^p \equiv a \pmod p$

Demonstrações

·        Demonstração 1

Se p|a, então

  $a^p \equiv a \equiv 0 \pmod p$

 Caso contrário,

$\varphi(p) = p-1$, $a^{p-1} \equiv 1 \pmod p$

e novamente

$a^p \equiv a \pmod p$.

·        Demonstração 2  

     Esta é outra demonstração do Pequeno Teorema de Fermat, feita por indução em a, usando o binómio de Newton e algumas propriedade de números binomiais.

Se 0 < i < p temos

\begin{displaymath}\binom{p}{i} = \frac{p!}{i! (p-i)!} \equiv 0 \pmod p\end{displaymath}

pois há um factor p no numerador que não pode ser  cancelado com nada que apareça no denominador. 
Os casos a = 0 e a = 1 do teorema são triviais. 
Supondo válido o teorema para a, temos

\begin{align}(a+1)^p &= a^p + \binom{p}{1} a^{p-1} + \cdots + \binom{p}{p-1} a + 1 \notag\\ &\equiv a^p + 1 \notag\\ &\equiv a + 1 \pmod p \notag \end{align}
 

  e a indução está completa.