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!
Follow Math Help Forum on Facebook and Google+
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:
Originally Posted by o_O Let: and By definition: Since and , then . You mean "n", not "m" here, don't you? 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:
View Tag Cloud