# 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:)