Mostre que se d=m d c(a, b) divide b, então as congruências lineares
a x equiv b(bmod n) e (ad) x equiv(ad)(bmod md)
tem as mesmas soluções.

Passo 1

O enunciado pede para mostrar que, se d=gcd(a,n) divide b, então as duas congruências
a x equiv b pmod n
e
ad,x equiv bd pmodnd
têm exatamente o mesmo conjunto de soluções. Vamos usar o fato de que
  1. ;a xequiv bpmod n se e só se nmid (a x - b).
  2. Quando dmid a,n,b, podemos “dividir” a congruência por d.

Passo 2

Suponha que x satisfaz
a x equiv b pmod n,
isto é,
n mid (a x - b)
Como dmid n e dmid a e dmid b, podemos escrever
n = dcdotnd, a = dcdotad, b = dcdotbd
Logo
dcdotnd ;m|; dl(adx - bdr) Longrightarrow nd;m|;l(adx - bdr),
ou seja,
ad,x equiv bd pmodnd
Logo qualquer solução da primeira é solução da segunda.

Passo 3

Reciprocamente, suponha que
ad,x equiv bd pmodnd
Então
nd;m|;l(adx - bdr) Longrightarrow dcdotnd;m|;dl(adx - bdr),
isto é,
nmid (a x - b),
portanto
a x equiv b pmod n
Assim toda solução da segunda congruência é solução da primeira.

Passo 4

Concluímos que cada x satisfaz a primeira congruência se, e somente se, satisfaz a segunda. Logo elas são equivalentes e têm exatamente o mesmo conjunto de soluções.

Resposta

As congruências
a x equiv b pmod n e ad,x equiv bd pmodnd
são equivalentes, isto é, têm o mesmo conjunto de soluções.

Exercícios relacionados