Encontre todos os inteiros
que satisfazem
Passo 1
O enunciado pede: encontre todos os inteiros
que satisfazem a congruência
Informações fornecidas:
- Módulo:
. - Coeficiente de
: . - Lado direito:
.
A pergunta é: listar todos os inteirosque tornam verdadeira essa congruência.
Passo 2
O que significa
? Significa que
divide a diferença
. Em outras palavras, existe um inteiro
tal que
Essa é uma equação diofantina linear em
e
. Resolver a congruência é equivalente a encontrar todas as soluções inteiras dessa equação.
Passo 3
Antes de tentar resolver, é útil verificar a condição de existência de solução para uma congruência linear
: existe solução se, e somente se,
divide
.
Calcule
. Como
é primo em relação a
, temos
Como
divide
, a congruência tem solução e, porque o gcd é
, haverá exatamente uma classe de congruência (ou seja, uma solução única módulo
).
Passo 4
Para obter a solução basta multiplicar ambos os lados pela inversa multiplicativa de
módulo
. A inversa de
módulo
é um inteiro
tal que
Podemos achar
por tentativa (ou pelo algoritmo de Euclides estendido). Testando pequenos valores:
Então
é a inversa de
módulo
.
Multiplicando a congruência dada por
obtemos
Calcule
e reduza módulo
:
Portanto
Passo 5
Escrevendo a solução em forma explícita de inteiros: todos os inteiros congruentes a
módulo
resolvem a congruência. Assim a família completa de soluções é
Verificação rápida: para
temos
e
(porque
), logo funciona. Valores como
também servem, pois
e
.
Dica prática para a prova: quando
, ache a inversa de
módulo
(por tentativa se
for pequeno, ou por Euclides estendido) e multiplique ambos os lados; isso dá a única classe solução módulo
.