Encontre todas as soluções das seguintes congruências lineares:
.
Passo 1
O enunciado pede: "Encontre todas as soluções da congruência linear
Informações dadas:
- O coeficiente multiplicador é
. - O termo à direita é
. - O módulo é
.
A pergunta é: quais inteirossatisfazem essa congruência, descritos de forma completa (todas as classes residuais modulo )?
Passo 2
Primeiro passo prático e teórico: calcular o máximo divisor comum entre
e
.
Calculemos:
logo
.
Teorema importante (explicação didática): para a congruência existe solução se, e somente se,
divide
. Se
não há solução. Se
, então existem exatamente
soluções distintas modulo
, e podemos reduzir a congruência dividindo tudo por
.
Teorema importante (explicação didática): para a congruência
Aqui
e
divide
(porque
), então existem soluções — exatamente
classes distintas modulo
.
Passo 3
Dividimos a congruência por
para simplificar. Dividindo
por
obtemos a congruência equivalente (com módulo dividido por
):
ou seja
Explicação didática: essa redução é válida porque estamos dividindo coeficiente, termo e módulo pelo mesmo divisor comum; assim as soluções da congruência reduzida correspondem às soluções da original, agrupadas em classes separadas por
.
Passo 4
Agora resolvemos a congruência reduzida
. Como
, o número
tem inverso multiplicativo módulo
. Se
é esse inverso, a solução é
Vamos achar
usando o algoritmo de Euclides estendido (ou observação direta). Calculando:
Da equação
vemos que
é um coeficiente tal que
. Assim
(pois
). Portanto o inverso de
módulo
é
.
Passo 5
Multiplicamos pelo inverso para obter a solução particular modulo
:
Calcule
:
Reduzindo modulo
:
Logo
Isso nos dá todas as soluções da congruência reduzida — são todas as classes
com
.
Passo 6
Agora voltamos ao módulo original
. Como vimos no Passo 2, existem exatamente
soluções diferentes módulo
. Elas vêm de tomar as soluções da congruência reduzida e acrescentar multiplos de
até obter as
classes distintas modulo
. Assim as soluções (representantes) são:
Tomando
(essas três dão as classes distintas modulo
):
-
: . -
: . -
: .
Esses três valores representam as três classes distintas módulo
.
Passo 7
Verificação rápida (checar que as três realmente funcionam):
Todas dão resto
módulo
, portanto estão corretas.