8
$\begingroup$

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!

3 Answers 3

2

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

  • 0
    Thanks, that gets me to the answer that @quanta gave! Appreciate it!2011-03-07
7

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)

  • 0
    @Christoph, I've added more details2011-03-08
5

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.

  • 0
    @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.2011-03-08