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!

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