Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?


share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
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)

share|improve this answer
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$.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.