Determine se as congruências lineares abaixo possuiem soluções. Em caso afirmativo, encontre todas as soluções incongruentes:
Passo 1
O enunciado pede para verificar se a congruência linear
tem solução e, em caso afirmativo, encontrar todas as soluções incongruentes.
Informações dadas:
Informações dadas:
- Coeficiente
. - Termo independente
. - Módulo
.
Passo 2
Regra básica (teoria mastigada): a congruência linear
tem solução se, e somente se, o máximo divisor comum
divide
. Se existir solução, há exatamente
classes incongruentes módulo
. Vou aplicar isso ao nosso caso.
Calculemos
Para achar
faça a fatoração mental ou use o algoritmo de Euclides:
e
, então
Como
e
, verificamos se
divide
:
divide
. Portanto, pelo critério, a congruência tem solução.
Passo 3
Redução da congruência (motivo e método): quando
divide
, podemos dividir toda a congruência por
para obter uma congruência equivalente com coeficiente e módulo menores. Defina
No caso:
A congruência reduzida é
Essa congruência é equivalente à original no sentido de que cada solução desta gera soluções da original (vou explicitar como no próximo passo).
Passo 4
Resolver a congruência reduzida: como
, o coeficiente
tem inverso multiplicativo módulo
. Definição de inverso: um número
é inverso de
módulo
quando
Aqui, verifique que
portanto
é o inverso de
modulo
. Multiplicando a congruência reduzida por esse inverso, obtemos
ou seja
Isso nos dá a solução geral da congruência reduzida: todos os inteiros da forma
, com
.
Passo 5
Voltar à congruência original e enumerar as classes incongruentes módulo
: a teoria diz que, se a congruência reduzida tem uma solução
módulo
, então as soluções da congruência original são exatamente as classes
onde
. No nosso caso
,
e
. Logo as soluções mod
são
Para
temos
.
Para temos
.
Para
Verificação rápida (para ficar tranquilo):
portanto ambas funcionam. Não existem outras classes incongruentes modulo
porque o teorema garante exatamente
classes.
Passo 6
Resumo didático final (como aplicar isso numa prova): ao ver
,
- Calcule
. - Se
, não há solução. - Se
, divida tudo por e resolva a congruência reduzida com , , . Como haverá inverso de módulo e uma solução módulo . - As soluções da congruência original são
para , totalizando classes incongruentes módulo .
No problema concreto isso deu as duas classes apresentadas no passo anterior.
Resposta
Sim.
As soluções incongruentes módulo são
e
.
As soluções incongruentes módulo