Considere o sistema de congruências
. Suponha que
. Aplique o método do algoritmo chinês do resto para mostrar que:
(a) se
divide
então o sistema tem solução;
(b) se
NÃO divide
então o sistema NÃO tem soução.
(a) se
(b) se
Passo 1
O enunciado pede para estudar o sistema de congruências
onde
.
O conteúdo aqui é o Teorema Chinês dos Restos em sua forma geral (moduli não necessariamente primos entre si) e a teoria de resolução de congruências lineares. Precisaremos usar que a congruência
O conteúdo aqui é o Teorema Chinês dos Restos em sua forma geral (moduli não necessariamente primos entre si) e a teoria de resolução de congruências lineares. Precisaremos usar que a congruência
tem solução se, e somente se,
divide
.
Passo 2
Da primeira congruência tiramos que
para algum inteiro
. Essa é a forma geral de todos os
que satisfazem a primeira linha.
Passo 3
Substituindo
na segunda congruência obtemos
Passo 4
Chamar
. A congruência
tem solução se, e somente se,
divide
.
- Se
, há solução para e, portanto, há solução para . - Se
, não existe que torne a congruência verdadeira, e então o sistema não tem solução.
Passo 5
Quando
, podemos fazer
Como
, existe o inverso de
módulo
, digamos
. Uma solução para
é
e, daí,
é uma solução do sistema. Todas as soluções ficam congruentes módulo
.
Resposta
(a) Se
, então o sistema tem solução.
(b) Se , então o sistema não tem solução.
(b) Se