Resolva cada sistema de congruências abaixo:
Passo 1
O enunciado dá o seguinte sistema de congruências e pede todas as soluções
Informações relevantes que temos:
- As congruências são .
- As modulações envolvidas são
e . - A pergunta é: quais são todos os inteiros
que satisfazem simultaneamente essas duas condições? (Normalmente iremos expressar a solução como uma congruência .)]
Passo 2
Vamos partir da primeira congruência e escrever a forma geral de
que ela impõe. A congruência
significa que
difere de
por um múltiplo de
. Portanto podemos escrever
onde
é um inteiro arbitrário. Aqui
é a variável inteira que conta quantos passos de tamanho
a partir de
nós damos para gerar todos os
que satisfazem a primeira congruência.
Passo 3
Agora substituímos
na segunda congruência para impor também essa condição:
Subtraindo
dos dois lados obtemos uma congruência mais simples em
:
Então precisamos resolver essa congruência linear em
: encontrar inteiros
tais que
seja múltiplo de
.
Passo 4
Para resolver
usamos o conceito de inverso multiplicativo módulo
. Se existe um número
tal que
, então multiplicando a congruência por
obtemos
.
Podemos encontrar
por tentativa (os números são pequenos):
Logo
é o inverso de
módulo
. (Também se pode ver com o algoritmo de Euclides:
implica
, e
.)
Portanto de
obtemos
Passo 5
A congruência
significa que existem inteiros
tais que
Substituindo esse
na expressão
obtemos
Portanto todas as soluções
do sistema são os números da forma
com
.
Aqui
aparece porque é o mínimo múltiplo comum de
e
(ou seja,
), então as soluções se repetem a cada
unidades. Como
e
são coprimos, a solução é única módulo
.
Passo 6
Vamos checar uma solução concreta para ter certeza: tomar
dá
.
Funciona. Assim a solução geral está correta.
Passo 7
Resumo do procedimento (receita prática para a prova):
- Expresse uma congruência na forma
(aqui ). - Substitua na outra congruência e reduza para uma congruência simples em
. - Resolva essa congruência usando inverso modular (por tentativa ou Algoritmo de Euclides).
- Volte à expressão de
para obter a solução geral e escreva como congruência modulo dos módulos (aqui modulo ).