# Congruence Proof

• May 14th 2009, 07:38 PM
wolfamdeus
Congruence Proof
If a $\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, 09:27 PM
o_O
Let: $d_1 = \gcd (a,n) > 0$ and $d_2 = \gcd (b,n) > 0$

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

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

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

So: $d_1 \mid d_2$

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

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

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

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

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

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

Quote:

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

So: $d_1 \mid d_2$

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

This implies: $d_1 = d_2$