Sejam
inteiros e
um primo tais que
. Mostre que uma solução da congruência
é
.
Passo 1
O enunciado dá as seguintes informações:
-
e são inteiros. -
é um primo. -
(ou seja, não divide ).
A pergunta que precisamos responder é: mostrar que uma solução da congruência
é
Passo 2
Vamos primeiro entender o que significa “solução” da congruência e a ideia de inverso multiplicativo:
- Dizer que
é solução de significa que, ao multiplicar por e subtrair , o resultado é múltiplo de . - Se existir um número
tal que
então
é o inverso multiplicativo de
módulo
. Nesse caso, multiplica-se a congruência
por
e obtém-se
. Assim, encontrar uma solução para
reduz-se a encontrar um inverso de
módulo
.
Passo 3
Apresento agora um resultado fundamental (que será usado): para
primo e
vale
Explicação curta e intuitiva (prova clássica): considere os resíduos
módulo
. Multiplicar cada um por
(com
invertível módulo
) apenas permuta esses resíduos sem produzir nenhum múltiplo de
. Portanto o produto dos elementos da sequência coincide módulo
com o produto dos mesmos elementos multiplicados por
, isto é,
Como
não é múltiplo de
, pode-se “cancelar” esse fator (porque é invertível módulo
) e obter
.
Passo 4
A partir de
obtemos diretamente que
Isto mostra que
é um inverso multiplicativo de
módulo
: ou seja,
Passo 5
Agora usamos esse inverso para resolver a congruência. Multiplique a congruência original
por
em ambos os lados:
Pela associatividade,
Mas sabemos que
, logo
ou seja
Portanto
(mod
) é de fato uma solução.
Passo 6
Pequeno exemplo numérico para fixar a ideia: tome
,
,
. Então
. Calculando módulo
temos
. Logo
. Conferindo:
, que é exatamente
. Funciona!