# Congruence Proof

• May 14th 2009, 06:38 PM
wolfamdeus
Congruence Proof
If a $\displaystyle \equiv$ b (mod n), prove that gcd(b,n) = gcd(a,n).
I've tried working with the relationship between these equations but haven't had much luck. Thanks for any help in advance!
• May 14th 2009, 08:27 PM
o_O
Let: $\displaystyle d_1 = \gcd (a,n) > 0$ and $\displaystyle d_2 = \gcd (b,n) > 0$

By definition: $\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$

Since $\displaystyle d_1 \mid a$ and $\displaystyle d_1 \mid km$, then $\displaystyle d_1 \mid b$.

But this means $\displaystyle d_1$ is a common divisor of both $\displaystyle b$ and $\displaystyle n$. Every common divisor of two integers divides their greatest common divisor.

So: $\displaystyle d_1 \mid d_2$

You can similarly show that: $\displaystyle d_2 \mid d_1$

This implies: $\displaystyle d_1 = d_2$
• May 15th 2009, 06:12 AM
HallsofIvy
Quote:

Originally Posted by o_O
Let: $\displaystyle d_1 = \gcd (a,n) > 0$ and $\displaystyle d_2 = \gcd (b,n) > 0$

By definition: $\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$

Since $\displaystyle d_1 \mid a$ and $\displaystyle d_1 \mid km$, then $\displaystyle d_1 \mid b$.

You mean "n", not "m" here, don't you?

Quote:

But this means $\displaystyle d_1$ is a common divisor of both $\displaystyle b$ and $\displaystyle n$. Every common divisor of two integers divides their greatest common divisor.

So: $\displaystyle d_1 \mid d_2$

You can similarly show that: $\displaystyle d_2 \mid d_1$

This implies: $\displaystyle d_1 = d_2$