Pegue o número 2 e eleve a potências cada vez maiores. Divida cada resultado por 7 e anote o resto:

Potência $2^1$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$
Valor 2 4 8 16 32 64
Resto por 7 2 4 1 2 4 1

Em $2^6$, o resto é 1. Agora tente com 3 e o primo 5: $3^4=81$, que deixa resto 1 na divisão por 5. E com 10 e o primo 13: $10^{12}=1\,000\,000\,000\,000$, que também deixa resto 1 na divisão por 13.

Coincidência? Não. É o pequeno teorema de Fermat.

O enunciado

Se $p$ é um número primo e $a$ é um inteiro que não é múltiplo de $p$, então $a^{p-1}$ deixa resto 1 na divisão por $p$. Em notação de congruências, criada por Gauss em 1801:

$$a^{p-1}\equiv1\pmod p.$$

O nome “pequeno” serve só para distingui-lo do último teorema. Na prática, o pequeno é muito mais útil.

Escolha a base e um primo. Quando a base é múltipla do primo, a hipótese da versão com expoente p − 1 não se aplica.

Uma carta sem prova

Fermat anunciou o teorema numa carta de 18 de outubro de 1640 ao matemático Bernard Frénicle de Bessy. Como de costume, não mostrou a demonstração:

Eu lhe enviaria a demonstração, se não temesse que fosse longa demais.

— Fermat, carta a Frénicle de Bessy (1640)

A primeira prova publicada foi de Leonhard Euler, em 1736, quase cem anos depois. Soube-se mais tarde que Leibniz também tinha uma prova, por volta de 1683, que nunca publicou.

Uma prova por embaralhamento

Vamos provar o teorema para $p=7$ e $a=3$; o argumento geral é idêntico.

Escreva os números $1,2,3,4,5,6$. Multiplique cada um por 3 e pegue o resto por 7:

$$3,\ 6,\ 9\to2,\ 12\to5,\ 15\to1,\ 18\to4.$$

Os restos são $3,6,2,5,1,4$: os mesmos números de antes, embaralhados. Isso sempre acontece. Nenhum resto pode ser 0, porque $p$ não divide $a$ nem $k$. E não há restos repetidos, porque se $ai$ e $aj$ deixassem o mesmo resto, $p$ dividiria $a(i-j)$ e, portanto, $i-j$, o que é impossível para dois números distintos entre 1 e $p-1$.

Como os dois conjuntos são iguais, os produtos também deixam o mesmo resto:

$$(3\cdot1)(3\cdot2)\cdots(3\cdot6)\equiv1\cdot2\cdots6\pmod7,$$

ou seja, $3^6\cdot6!\equiv6!\pmod7$. Como 7 é primo e não divide $6!$, podemos cancelar o $6!$ e concluir que $3^6\equiv1\pmod7$. Confira: $3^6=729=7\cdot104+1$.

Contas enormes com pouco esforço

Quanto é o resto de $3^{100}$ na divisão por 7? Sem o teorema, seria preciso calcular um número de 48 algarismos. Com ele: $3^6\equiv1$, e $100=6\cdot16+4$. Então

$$3^{100}=\left(3^6\right)^{16}\cdot3^4\equiv1^{16}\cdot81\equiv4\pmod7.$$

Essa capacidade de reduzir potências gigantescas é a base do sistema RSA, que protege compras e senhas na internet. O RSA usa uma generalização do teorema feita por Euler, contada na trilha de Euler.

Cuidado com a volta

Se $p$ é primo, então $a^{p-1}\equiv1$. Mas a recíproca é falsa: um número pode passar no teste sem ser primo. O menor exemplo traiçoeiro é $561=3\cdot11\cdot17$, que satisfaz $a^{560}\equiv1\pmod{561}$ para todo $a$ sem fatores em comum com 561. Números assim se chamam números de Carmichael. Por isso o teorema serve para mostrar que um número não é primo, mas não basta para mostrar que é.

Exercício: qual o resto de 3¹⁰ na divisão por 11?

11 é primo e não divide 3, então $3^{10}\equiv1\pmod{11}$. O resto é 1. Confira: $3^{10}=59\,049=11\cdot5368+1$.

Exercício: qual o resto de 2¹⁰⁰ na divisão por 13?

$2^{12}\equiv1\pmod{13}$ e $100=12\cdot8+4$. Então $2^{100}\equiv2^4=16\equiv3\pmod{13}$. O resto é 3.

Fontes: biografia de Fermat, MacTutor.

Todos os tópicos de Fermat · ← Máximos e mínimos: o retângulo de maior área · Números de Fermat: uma conjectura e um contraexemplo →

Créditos das imagens.