Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$ [duplicate]

Solution 1:

Another way to understand $a \equiv b \pmod n$ is that there is some $k$ such that $a = b + kn$. This is the view in terms of Ideals.

Now you can conclude by proving that $$(b + kn,n) = (b,n).$$

Two useful facts about gcd for every $a,b$:

$\exists x,y,\,\,(a,b)=ax+by.$
$\forall x,y,\,\,(a,b)|ax+by.$

Now the idea is to prove that both $(b+kn,n)|(b,n)$ and $(b,n)|(b+kn,n)$ which implies that $(b+kn,n) = (b,n).$

You've already shown the first one $(b+kn,n)=(b+kn)x+ny=bx+knx+ny=bx+n(kx+y)$ hence $(b,n)|(b+kn,n).$

You can use the same algebra methods to prove the second part and conclude. (HINT: u = u + v - v)

Solution 2:

If $\rm\ d\ |\ n\ |\ a\!-\!b\ $ then $\rm\ d\ |\ a \!\iff\! d\ |\ b, \ $ i.e. $\rm\bmod d\!:\ $ if $\rm\ a\equiv b\ $ then $\rm\ a\equiv 0\!\iff\! b\equiv 0$

So $\rm\, \{n,a\},\ \{n,b\}\ $ have the same common divisors $\rm\,d,\,$ so the same greatest common divisor.

Remark $\ $ Note how it simplifies after eliminating the less intuitive divisibility relations in favor of familiar equations (here congruences). $\ $ After converting it to manipulation of equations it is completely trivial, viz. if $\rm\ a \equiv b\ $ then $\rm\ n,a\equiv 0 \iff n,b \equiv 0.\:$ That illustrates the tremendous power of congruences - they allow us to transform diverse problems to equational form - allowing us to reuse our well-honed intuition on manipulating (integer) equations. To succeed in number theory and algebra it is essential to master such techniques. They lead to powerful methods of "modular reduction" - an algebraic way of "dividing and conquering" - reducing problems to simpler problems that (hopefully) combine to yield the complete solution.