# Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$

My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints?

Thanks!

-

HINT $\:$ If $\rm\ d\ |\ n\ |\ a-b\$ then $\rm\ d\ |\ a\ \iff\ d\ |\ b\:, \$ i.e. $\:$ if $\rm\ a\equiv b\$ then $\rm\ a\equiv 0\ \iff\ b\equiv 0\ \ \ (mod\ d)$

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

REMARK $\$ Note how much simpler the problem becomes after eliminating the obfuscated divisibility relations in favor of equations (here congruences). $\$ After converting it to manipulation of equations it is completely trivial, viz. if $\rm\ a = b\$ then $\rm\ a = n = 0\ \iff\ b = n = 0\:.\:$ That is the tremendous power of congruences - they allow us to transform diverse problem to equational form - allowing us to reuse our well-honed intuition on manipulating (integer) equations. To succeed in number theory and algebra it is absolutely 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.

-
In other words, if d divides a-b, then d divides a if and only if d also divides b. I understand that, I think. I am not sure where to go from there though. How does that relate to the linear combination of a and b? Thank you for helping! –  Christoph Mar 7 '11 at 23:37
I picked yours as the accepted answer because of the way of thinking. Thanks for helping me in that. Thanks to everyone else, especially quanta for being very helpful! –  Christoph Mar 8 '11 at 2:00
@Chris: The hint shows how to deduce that $\rm\ d\ |\ a,n\ \iff\ d\ |\ b,n\:,\:$ Thus both pairs have the same set $\rm\:C\:$ of common divisors, hence the same gcd, since the gcd is simply the greatest common divisor, i.e. $\rm\: max\ C\:.\:$ Note that this method doesn't employ the Bezout linear representation of the gcd. As such it works more generally, in any domain where gcds exist. –  Bill Dubuque Mar 8 '11 at 2:28

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)

-
Hm trying to wrap my head around that. I think that makes sense intuitively. I guess from here I break that up into its linear combination? $(b+kn,n)=(b+kn)x+ny=bx+knx+ny$. Now I have to get rid of the $knx$...hmm –  Christoph Mar 7 '11 at 23:42
@Christoph, I've added more details –  quanta Mar 8 '11 at 0:20

We know that $a-b = nx$. So $a-nx = b$ and $b+nx = a$.

-
Thanks, that gets me to the answer that @quanta gave! Appreciate it! –  Christoph Mar 7 '11 at 23:34