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
$\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 PMbill77
thanks for the help, i now know what to conclude:)