# congruence

• Nov 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).
• Nov 15th 2008, 11:30 AM
o_O
$\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow a = b + km$ for some integer k.

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

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

This means that any common divisor of $\displaystyle b$ and $\displaystyle m$ is less than $\displaystyle d$. Can you conclude?
• Nov 15th 2008, 12:14 PM
bill77
thanks for the help, i now know what to conclude:)