Em quais condições o sistema de congruências abaixo admite solução
x equiv b1 & bmod m1 x equiv b2 & bmod m2

Passo 1

Nesse exercício, temos o sistema de congruências
x equiv b1 bmod m1 x equiv b2 bmod m2
O conteúdo envolvido é o Teorema do Resto Chinês generalizado e congruências lineares. Vamos usar que uma congruência do tipo a k equiv c bmod m tem solução se, e somente se, gcd(a,m) divide c.

Passo 2

Para compatibilizar as duas congruências, escrevemos x = b1 + k,m1 para algum inteiro k. Substituindo na segunda congruência, obtemos:
b1 + k,m1 equiv b2 bmod m2
Que é equivalente à congruência linear m1k equiv b2 - b1 bmod m2.

Passo 3

Essa congruência linear m1k equiv b2 - b1 bmod m2 só tem solução em k se e somente se gcd(m1,m2) divide b2 - b1. Denotando d = gcd(m1,m2), a condição de existência é d mid (b2 - b1).

Passo 4

Concluímos então que o sistema original admite solução se, e somente se, gcd(m1,m2) divide b2 - b1. Nessas condições, as soluções são únicas módulo lcm(m1,m2).

Resposta

O sistema tem solução se, e somente se, gcd(m1,m2) divide b2 - b1.

Exercícios de Livros Relacionados