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!
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$
You mean "n", not "m" here, don't you?
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$