Seja
um inteiro. Mostre que
se
, então
.
se
Passo 1
Vou listar claramente o que o enunciado dá e o que pede, sem resolver nada ainda.
- Dado:
é um inteiro tal que . - Pedido: mostrar que
.
Informações relevantes extraídas do enunciado:
- O módulo é
. - A condição
significa que é invertível módulo (não divide 5 nem 7). - Não há outro dado numérico.
Passo 2
Idéia geral que vamos usar (explicação didática do resultado que será aplicado).
Existe um resultado geral que diz que, para todo inteiro
e todo inteiro
com
, vale
onde
é a função totiente de Euler (número de inteiros entre
e
que são coprimos com
). Esse resultado é conhecido como o Teorema de Euler. Vamos explicar o que é
e provar por que o teorema é verdade de maneira elementar.
Passo 3
O que é
e como calcular
.
- Definição:
é o número de inteiros tais que . - Propriedade útil: se
é primo então porque todos os inteiros são coprimos com . - Para produto de primos distintos,
é multiplicativa: se então . No caso de potências de primo vale .
Aplicando isso a
(5 e 7 são primos e são coprimos entre si):
Também é possível usar a fórmula
e obter o mesmo:
.
Passo 4
Prova elementar do Teorema de Euler (por que
quando
).
Construa o conjunto dos resíduos reduzidos módulo
:
onde cada
satisfaz
e
. Multiplicar todos os elementos de
por
módulo
dá outro conjunto
Porque
, a multiplicação por
modulo
é uma permutação dos elementos de
: nenhum produto
é congruente a
(pois
é coprimo a
) e se
então, multiplicando por inverso de
modulo
, obtemos
, logo
. Assim os dois produtos abaixo são congruentes módulo
:
No lado esquerdo podemos tirar
em fator:
Agora note que
é coprimo com
(produto de números cada um coprimo com
), então esse produto tem inverso multiplicativo módulo
. Cancelando (ou multiplicando ambos os lados pelo inverso), obtém-se
Isso prova o Teorema de Euler.
Passo 5
Aplicando o Teorema de Euler ao caso concreto
.
Temos calculado que
. Pela prova do Teorema de Euler, para qualquer inteiro
com
vale
Substituindo
obtemos
Passo 6
Comentário didático extra e alternativa curta usando primos (opcional, para fixar a ideia).
- Como
e , temos e . Pelo pequeno teorema de Fermat:
Como
, segue
e
, e portanto
(pelo CRT). Isso é ainda mais forte que o pedido
; em particular
. Essa via alternativa ajuda a entender que o expoente
aparece naturalmente por
, mas às vezes há expoentes menores que também funcionam.