Seja
um inteiro. Mostre que
.
Passo 1
O enunciado dá um inteiro
e pede para mostrar que
Informações relevantes que temos a partir do enunciado:
-
é um inteiro arbitrário (pode ser múltiplo de ou não). - O módulo é
, que é um número primo. - Precisamos provar a congruência para todo inteiro
.
Passo 2
Primeiro tratemos o caso simples: suponha que
divida
. Então
. Nesse caso:
logo
porque ambos são congruentes a
. Portanto o enunciado é verdadeiro quando
.
Passo 3
Agora suponha que
não divide
, ou seja,
. Vamos usar um fato fundamental (que vou demonstrar de forma elementar): para um primo
e inteiro
com
vale
Aqui
, então a afirmação será
.
Explicação e prova curta desse fato (argumento por rearranjo dos resíduos):
- Considere os números
. Como é primo, todos esses números são não-nulos módulo e formam o conjunto completo de representantes das classes invertíveis modulo . - Multiplicando cada um desses números por
(e reduzindo módulo ) obtemos . Como , a multiplicação por permuta essas classes: os produtos são congruentes (em alguma ordem) a módulo . - Portanto o produto dos
números originais é congruente ao produto dos produtos:
- No lado direito há
fatores , logo
- Como
não é múltiplo de , podemos “cancelar” esse produto (formalmente, existe inverso multiplicativo), obtendo
Isso estabelece a versão necessária do Teorema de Fermat para
.
Passo 4
Com
(quando
), reduzimos o expoente
. Observe que
Logo
Reducindo módulo
e usando
obtemos
Passo 5
Juntando os dois casos:
- Se
, então . - Se
, então por razão acima .
Portanto, para todo inteiro
vale
.