Resolva a congruência
.
Passo 1
O que o enunciado pede: resolver a congruência
, ou seja, encontrar todos os inteiros
que satisfazem essa relação módulo
.
Informações dadas: o coeficiente do é
, o resto desejado é
e o módulo é
.
Meta explícita: achar a(s) classe(s) de solução módulo
.
Informações dadas: o coeficiente do
Meta explícita: achar a(s) classe(s) de solução
Passo 2
Entendimento da condição necessária e estratégia: para resolver
precisamos saber se
tem inverso multiplicativo módulo
. Isso depende do máximo divisor comum
. Se
, então
é invertível modulo
e existe uma solução única modulo
. Se
, seria preciso verificar se
divide
e então reduzir. Vamos calcular o
usando o algoritmo de Euclides.
Cálculo do
:
Da última linha não-nula, concluímos que
Como o
é
,
tem inverso módulo
e haverá exatamente uma solução na classe modulo
.
Passo 3
Encontrar o inverso de
módulo
usando a retro-substituição (algoritmo extendido de Euclides). Das igualdades acima temos:
Mas
veio de
. Substituindo:
Desenvolvendo:
Isso significa que, reduzindo módulo
,
Portanto
é um inverso multiplicativo de
modulo
(poderíamos usar
também).
Verificação rápida:
e
porque
.
Passo 4
Aplicar o inverso à congruência original para isolar
. Multiplicando ambos os lados de
pelo inverso
obtemos
Calcule
:
Reduzindo modulo
:
Logo
Passo 5
Checagem final: substituir
na congruência inicial:
Reduzindo módulo
:
. Portanto
, confirma que a solução está correta. Como
, essa é a solução única na classe modulo
.