# Math Help - Congruence Proof

1. ## 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!

2. 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$

3. 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?

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$