Mostre que se a equiv b(bmod n) então mdc(a, m)=mdc(b, m).

Passo 1

O enunciado quer que a gente mostre que, dados inteiros a, b e m, se
a equiv b pmodm
então
gcd(a,m)=gcd(b,m)
Vamos usar a definição de congruência (divisibilidade) e a definição de máximo divisor comum como maior elemento do conjunto dos divisores positivos comuns.

Passo 2

Da congruência
a equiv b pmodm
segue que
m mid (a-b),
ou seja, existe um inteiro k tal que
a - b = k,m
Agora, seja d um divisor comum de a e m. Então
d mid a e d mid m
Como dmid m e dmid (a-b)=k,m, concluímos que dmid(a-b). Mas então,
dmid a e dmid(a-b) ;Longrightarrow; dmidl[a - (a-b)r] ;Longrightarrow; dmid b
Portanto, todo divisor comum de a e m também divide b, ou seja, é divisor comum de b e m.

Passo 3

O argumento anterior vale de forma simétrica trocando a por b. Logo, todo divisor comum de b e m também divide a. Concluímos que os conjuntos de divisores comuns de (a,m) e de (b,m) são exatamente os mesmos. Como o máximo divisor comum é o maior número inteiro positivo nesse conjunto, segue que
gcd(a,m)=gcd(b,m)

Resposta

gcd(a,m)=gcd(b,m).

Exercícios relacionados