Se a equiv b(bmod m1) e a cong b(bmod m2), mostre que a equiv b(bmod m), onde m=m m c(m1, m2). (Assim, se m d c(m1, m2)=1, então a equiv b (bmod m1 m2).)

Passo 1

O enunciado pede para mostrar que se
aequiv bpmodm1 e aequiv bpmodm2,
então
aequiv bpmodm,
onde m=lcm(m1,m2).
O que vamos usar é a definição de congruência (divisibilidade) e a propriedade de que, se dois números dividem um mesmo inteiro, então o mínimo múltiplo deles também o divide.

Passo 2

Da definição de congruência temos
m1mid (a-b)
e
m2mid (a-b).
Isto significa que existem k,linZ tais que
a-b=m1,k
e
a-b=m2,l.

Passo 3

Seja g=gcd(m1,m2).
Podemos escrever
m1=gx, m2=gy,
com gcd(x,y)=1.
Então as divisões acima ficam
a-b = g x k, a-b = g y l

Passo 4

Como gxmid (a-b), segue xmida-bg.
De modo análogo, ymida-bg.
E como gcd(x,y)=1, sabemos que xymida-bg.

Passo 5

Logo existe tinZ tal que
a-bg=x,y,t Longrightarrow a-b = g,x,y,t
Mas g,x,y=lcm(m1,m2), de modo que
a-b = lcm(m1,m2);,t,
ou seja lcm(m1,m2)mid (a-b).

Passo 6

Portanto
aequiv bpmodlcm(m1,m2)
No caso especial em que gcd(m1,m2)=1, temos lcm(m1,m2)=m1m2, de modo que
aequiv bpmodm1m2

Resposta

aequiv bpmodm, onde m=lcm(m1,m2).

Exercícios de Livros Relacionados