# Math Help - GCD proof

1. ## GCD proof

I am using == to denote congruency:
a== b (modm) meaning a is congruent to b (modm)
(or m divides a-b)

Suppose A is the set of integers
Let a,b,m be elements of A such that m>=2.

Prove "If a == b(modm) then gcd(a,m)=gcd(b,m)"

Everytime I try to do this, I get stuck.

Thank you for your help.

2. Originally Posted by mremwo
I am using == to denote congruency:
a== b (modm) meaning a is congruent to b (modm)
(or m divides a-b)

Suppose A is the set of integers
Let a,b,m be elements of A such that m>=2.

Prove "If a == b(modm) then gcd(a,m)=gcd(b,m)"

Everytime I try to do this, I get stuck.

Thank you for your help.
$a\equiv b\text{ mod }m\implies a=b+km$ and so $(a,m)=(b+km,m)=(b,m)$.

Is that not ok?

3. It took me some time to confirm (b + km, m) = (b, m). For any number d, d | b + km and d | m iff d | b and d | m.

4. I'm not sure if I'm missing something here. But isn't it as simple as to show that

(b + km, m) | (b,m)
AND
(b,m) | (b + km, m)

Is there something I'm missing plz?

5. Quite possible that I am missing something, but the easiest way to show (b + km, m) | (b,m) that I found was to show that d | b + km and d | m implies d | b and d | m.

6. Absolutely - but showing that is trivial. Isn't it? I'm just curious when you said it took you time - I have been reading your posts for quite some time and you sure have a reputation so wanted to be sure if there is somhething I have not understood?

7. I think this is easier (and perhaps slightly neater, as you don't have that lemma in the middle):

Note that,
$gcd(a, m) = ar_1 + ms_1$
and
$gcd(b, m) = br_2 + ms_2$.

Take the difference to see that $gcd(a, m) \equiv gcd(b, m) \text{ mod }m$. This gives you that $gcd(a, m)=gcd(b, m)$ as $gcd(a, m) < m$ and $gcd(b, m) < m$.

8. Originally Posted by aman_cc
Absolutely - but showing that is trivial. Isn't it?
Yes, it's pretty simple.