Is there anyone who can help me where to start. I'm having a hard time to figure this problem out. Thanks

Show that ifa, b,andmare integers such that m ≥ 2 and a ≡ b( mod m), then gcd(a,m) = gcd(b,m).

Printable View

- Nov 15th 2008, 11:04 AMbill77congruence
Is there anyone who can help me where to start. I'm having a hard time to figure this problem out. Thanks

Show that if*a, b,*and*m*are integers such that m ≥ 2 and a ≡ b( mod m), then gcd(a,m) = gcd(b,m). - Nov 15th 2008, 11:30 AMo_O
for some integer k.

Let . Since and , it follows from that and is thus a common divisor of and .

Let be**any**common divisor of and . With a similar argument, we have that . By definition, since is the**greatest**common divisor of and , we have that .

This means that any common divisor of and is less than . Can you conclude? - Nov 15th 2008, 12:14 PMbill77
thanks for the help, i now know what to conclude:)