# 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!

-

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)$

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 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 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