$\newcommand{\Z}{\mathbb Z}\newcommand{\cl}[1]{\overline{#1}}$Lema. Seja $p$ um número primo positivo e $a,b\in\Z$. Tem-se que
\[
(a+b)^p\equiv a^p+b^p\pmod p.
\]
Demonstração. Exercício.
Note que o lema acima pode ser expresso na estrutura $\Z_p$ (onde $p$ é primo). De fato, o lema é equivalente a afirmar que
\[
(\cl a+\cl b)^p=\cl a^p+\cl b^p\quad\mbox{para todo}\quad \cl a,\cl b\in\Z_p.
\]
Este mesmo lema é conhecido também como o Sonho do Calouro.
Teorema (Pequeno Teorema de Fermat). Se $p$ é um primo positivo e $a\in \Z$, então
\begin{equation}\label{eq:cong}
a^p\equiv a\pmod p.
\end{equation}
Além disso, se $p\nmid a$, então
\[
a^{p-1}\equiv 1\pmod p.
\]
Demonstração. Existe um único inteiro $a_0\in\{0,\ldots,p-1\}$ tal que $a\equiv a_0\pmod p$ e $a^p\equiv a_0^p\pmod p$. Possivelmente trocando $a$ com $a_0$, podemos assumir que $a\in\{0,\ldots,p-1\}$. Se $a=0$, então a afirmação será verdadeira trivialmente. Se $a>0$ é um número positivo, podemos escrever que $a=1+\cdots+1$ ($a$ vezes). Pelo lema anterior,
\[
a^p=(1+\cdots+1)^p\equiv 1^p+\cdots+1^p=1+\cdots +1=a\pmod p.
\]
Isso mostra que a primeira afirmação é válida.
Assuma agora que $p\nmid a$. Como no parágrafo anterior, podemos assumir sem perder generalidade que $a\in\{1,\ldots,p-1\}$ (note que $a\neq 0$ pela condição que $p\nmid a$). Em particular, $a$ é invertível módulo $p$; ou seja existe $b\in\{1,\ldots,p-1\}$ tal que $ab\equiv 1\pmod p$. Multiplicando a congruência \eqref{eq:cong} por $b$, obtemos que
\[
a^{p-1}\equiv (ba)a^{p-1}=ba^p\equiv ba\equiv 1\pmod p.
\]
Para um primo $p$, o Pequeno Teorema de Fermat pode ser escrita também na forma
\begin{eqnarray*}
\cl a^p&=&\cl a\quad\mbox{para todo}\quad \cl a\in \Z_p;\\
\cl a^{p-1}&=&\cl 1\quad\mbox{para todo}\quad \cl a\in \Z_p\setminus\{\cl 0\};
\end{eqnarray*}
O Pequeno Teorema de Fermat pode ser usado para dar um critério suficiente para decidir se um número é composto.
Teste. Assuma que $n\geq 2$ é um número natural. Se $b^{n-1}\not\equiv 1\pmod n$ para algum $b\in\{2,\ldots,n-2\}$, então $n$ é um número composto.
Observe que a congruência $b^{n-1}\equiv 1\pmod n$ pode ser checada para $n$ muito grande (veja Exercício 6 na Lista 7).
Exemplo. Seja $n=100000000000000000039000000005700000000000000002223$. Queremos saber se $n$ é um número primo ou ele é composto. Usando nossa implementação do algoritmo para calcular $2^{n-1}\pmod n$, obtemos que
\[
2^{n-1}\pmod n\equiv 49681379328330755781687237993204141263211912506416 \neq 1.
\]
Obtemos então que $n$ é um número composto. É muito mais difícil verificar que de fato
\[
n=100000000000000000039\cdot 10000000400000000000000000000057.
\]
Se $n\geq 2$ e $b^{n-1}\equiv 1\pmod n$, então o número $n$ chama-se pseudo primo na base $b$.
Exercício. Mostre para $2\leq b<n$ que se $n$ é pseudo primo na base $b$, então $\mbox{mdc}(n,b)=1$.
Algoritmo: Teste de de primalidade Fermat
Input: Número natural $n$.