Seja
um inteiro. Mostre que
se
, então
para todo
.
se
Passo 1
O enunciado dá que
é um inteiro com
e pede para mostrar que
para todo
.
Informações relevantes do enunciado:
-
é inteiro e (ou seja, é invertível módulo ); - precisamos provar a congruência para todos os inteiros
.
Passo 2
Definição e lema que vamos usar (explicado de forma elementar).
Definição: a função totiente de Euler
dá o número de inteiros entre
e
que são coprimos com
. Para
vamos calcular
no Passo 3.
Lema (Teorema de Euler, enunciado e ideia do porquê funciona):
Se , então
Se
Prova curta e intuitiva do lema (sem usar teoria de grupos):
- Considere o conjunto
formado pelos inteiros positivos menores ou iguais a que são coprimos com . Escreva . - Como
, a multiplicação por modulo leva cada a outro número coprimo com (pois se então ). Logo a lista é uma permutação de módulo . - Tomando o produto de todos os elementos dessa igualdade de conjuntos (mod
), obtemos
- Como cada
é coprimo com , o produto também é coprimo com e, portanto, tem inverso multiplicativo módulo . Podemos “cancelar” esse produto nas duas mãos da congruência, obtendo
Essa é a razão essencial do Teorema de Euler.
Passo 3
Cálculo de
.
Fatorando
temos
. A fórmula para
em termos de fatoração é
e, em geral, se
então
.
Aplicando a
:
Portanto
.
Passo 4
Aplicando o Teorema de Euler ao caso
.
Pelo Teorema de Euler (Passo 2), como
, vale
Como
(Passo 3), temos
Passo 5
Concluir para todo
.
Se
, então elevando ambos os lados à potência
obtemos
Isso vale para qualquer inteiro
. Assim a propriedade desejada está provada.
Passo 6
Observação alternativa (mais elementar, sem mencionar
explicitamente): os invertíveis módulo
são as classes representadas por
. Calculando
Logo todas as classes invertíveis têm quarta potência congruente a
módulo
, o que dá a mesma conclusão.