Em 1763, Euler estudou a função $\varphi(n)$ (o símbolo $\varphi$ veio depois, com Gauss): a quantidade de números de 1 a $n$ que não têm fator comum com $n$. Por exemplo, $\varphi(10) = 4$, porque de 1 a 10 só 1, 3, 7 e 9 servem. Ele provou que, se $a$ não tem fator comum com $n$, então

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

Veja a ideia com $n = 10$ e $a = 3$. Multiplique por 3 os números 1, 3, 7 e 9:

$$3 \cdot 1 = 3, \quad 3 \cdot 3 = 9, \quad 3 \cdot 7 = 21 \equiv 1, \quad 3 \cdot 9 = 27 \equiv 7 \pmod{10}.$$
No relógio de 10 horas, multiplicar por 3, 7 ou 9 só embaralha os números 1, 3, 7 e 9.

Os restos são 3, 9, 1 e 7: os mesmos quatro números, só embaralhados. Então o produto deles é o mesmo:

$$(3 \cdot 1)(3 \cdot 3)(3 \cdot 7)(3 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}$$ $$3^4 \cdot (1 \cdot 3 \cdot 7 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}.$$

Como $1 \cdot 3 \cdot 7 \cdot 9$ não tem fator comum com 10, dá para cancelar dos dois lados: $3^4 \equiv 1 \pmod{10}$. Confira: $3^4 = 81$, que deixa resto 1 na divisão por 10. O mesmo argumento funciona para qualquer $n$ e qualquer $a$ sem fator comum com $n$.

Quando $n$ é primo, $\varphi(n) = n - 1$ e o teorema vira o pequeno teorema de Fermat. Mais de 200 anos depois, em 1977, o teorema de Euler virou a base do RSA, o sistema de criptografia que protege compras pela internet e mensagens no celular.

Todos os tópicos de Leonhard Euler · ← O número de Fermat que não era primo · Outras contribuições e legado →

Créditos e fontes das imagens.