Considere a equação congruência linear
.
Encontre todas as soluções inconguentes.
Encontre todas as soluções inconguentes.
Passo 1
Resumo do enunciado: a gente precisa resolver a congruência linear
Conteúdo envolvido: teoria de congruências lineares, cálculo de
(máximo divisor comum), condição de existência, redução da congruência e inverso modular. Vamos usar o algoritmo de Euclides, dividir toda a congruência pelo
e achar o inverso.
Passo 2
Calcular
pelo algoritmo de Euclides:
87 = 58·1 + 29
58 = 29·2 + 0
Logo, .
87 = 58·1 + 29
58 = 29·2 + 0
Logo,
Passo 3
Condição de existência: a congruência
tem solução se, e só se,
divide
.
Como é inteiro, existem soluções.
Como
Passo 4
Dividimos tudo por 29 para simplificar:
Reduzindo
dá
. Então
Precisamos do inverso de
módulo
. Testando,
, logo
. Multiplicando ambos os lados por 2:
Passo 5
A solução geral da congruência reduzida é
Como estamos trabalhando módulo
, e dividimos por
, aparecem
soluções incongruentes no intervalo de
a
, correspondendo a
.
Resposta
As soluções incongruentes de
são
ou seja,