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!

Printable View

- May 14th 2009, 06:38 PMwolfamdeusCongruence 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 PMo_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 AMHallsofIvy
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$