congruence

Printable View

November 15th 2008, 11:04 AM
bill77

congruence

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).
November 15th 2008, 11:30 AM
o_O

$a \equiv b \ (\text{mod } m) \ \Leftrightarrow a = b + km$ for some integer k.

Let $d = (a,m)$ . Since $d \mid a$ and $d \mid m$ , it follows from $a = b+km$ that $d \mid b$ and is thus a common divisor of $b$ and $m$ .

Let $c$ be any common divisor of $b$ and $m$ . With a similar argument, we have that $c \mid a$ . By definition, since $d$ is the greatest common divisor of $a$ and $m$ , we have that $c \leq d$ .

This means that any common divisor of $b$ and $m$ is less than $d$ . Can you conclude?
November 15th 2008, 12:14 PM
bill77

thanks for the help, i now know what to conclude:)