Considere o sistema de congruências cx equiv a(bmod m) x equiv b(bmod n). Suponha que m d c(m, n)=d. Aplique o método do algoritmo chinês do resto para mostrar que:
(a) se d divide b-a então o sistema tem solução;
(b) se d NÃO divide b-a então o sistema NÃO tem soução.

Passo 1

O enunciado pede para estudar o sistema de congruências
x equiv a pmod m, x equiv b pmod n,
onde gcd(m,n)=d.
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
A,k equiv C pmod N
tem solução se, e somente se, gcd(A,N) divide C.

Passo 2

Da primeira congruência tiramos que
x equiv a pmod m Longrightarrow x = a + m,k
para algum inteiro k. Essa é a forma geral de todos os x que satisfazem a primeira linha.

Passo 3

Substituindo x = a + m,k na segunda congruência obtemos
a + m,k equiv b pmod n Longrightarrow m,k equiv b - a pmod n

Passo 4

Chamar d = gcd(m,n). A congruência
m,k equiv b - a pmod n
tem solução se, e somente se, d divide b-a.
  • Se dmid(b-a), há solução para k e, portanto, há solução para x.
  • Se dnmid(b-a), não existe k que torne a congruência verdadeira, e então o sistema não tem solução.

Passo 5

Quando dmid(b-a), podemos fazer
m' = md, n' = nd, De<a = b-ad
Como gcd(m',n')=1, existe o inverso de m' módulo n', digamos (m')^-1pmodn'. Uma solução para k é
k equiv (m')^-1,De<a pmodn',
e, daí,
x = a + m,k
é uma solução do sistema. Todas as soluções ficam congruentes módulo lcm(m,n)=m,n'.

Resposta

(a) Se dmid(b-a), então o sistema tem solução.
(b) Se dnmid(b-a), então o sistema não tem solução.

Exercícios relacionados