If a 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 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: and

By definition:

Since and , then .

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

So:

You can similarly show that:

This implies: - May 15th 2009, 06:12 AMHallsofIvy