# Prove: $a\equiv b\pmod{n} \implies \gcd(a,n)=\gcd(b,n)$

Proof: If $a\equiv b\pmod{n}$, then $n$ divides $a-b$. So $a-b=ni$ for some integer $i$. Then, $b=ni-a$. Since $\gcd(a,n)$ divides both $a$ and $n$, it also divides $b$. Similarly, $a=ni+b$, and since $\gcd(b,n)$ divides both $b$ and $n$, it also divides $a$.

Since $\gcd(a,n)$ is a divisor of both $b$ and $n$, we know $\gcd(a,n)\leq\gcd(b,n)$. Similarly, since $\gcd(b,n)$ is a divisor of both $a$ and $n$, we know $\gcd(b,n)\leq\gcd(a,n)$. Therefore, $\gcd(a,n)=\gcd(b,n)$.

Thanks for helping me through this one!

-

Let $a-b=ni$ like you say. Then $b=a-ni$, so since $\gcd(a,n)$ divides $a$ and $n$, it also divides $b$. So as a common divisor of $n$ and $b$, you must have $\gcd(a,n)\mid\gcd(b,n)$. Similarly, $\gcd(b,n)\mid\gcd(a,n)$, so necessarily $\gcd(a,n)=\gcd(b,n)$.

-
nicely put! I like that 2-directional approach. – ivan Feb 28 '13 at 17:33
@ivan Thanks, glad it helped. – Ben West Feb 28 '13 at 17:36

You're almost done. Note $\rm\: d\mid n,b\iff d\mid n,b\!+\!ni\:$ since if $\rm\:d\mid n\:$ then $\rm\:d\mid b\iff d\mid b\!+\!ni.\:$ Therefore we've deduced that $\rm\:n,b\:$ and $\rm\:n,b+ni\:$ have the same set D of common divisors d, therefore they have the same greatest common divisor (= max D).

-

HINT : Let $d = \gcd(b,n)$, then $b = dx$ and $n = dy$ for some $x$ and $y$

-