Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am currently reading a book on basic number theory and in the first chapter the author uses the fact that if $d \mid x$ and also $d\mid y$, then it is true that $d$ is a divisor to both sides of the equation: $$ x = y +r $$

I see that it is true, but how could you prove that? I mean, if $x$ and $y$ are even, then the $\gcd(x,y)$ is even and the rest $r = 0$, hence for any other divisor $c < \gcd(x,y)$ the rest $r$ will of course be even.

What about if $\gcd(x,y)$ is odd? Or is this a bad way to approach a proof for above statement? How would you do to prove it?

Best regards,

share|cite|improve this question
If $d$ divides $x,y$ ,let $\frac xX=\frac yY=d\implies r=x-y=d(X-Y)$ – lab bhattacharjee May 28 '13 at 18:10
By assumption, $d$ divides the left side of the equation, $x$. Since the two sides are equal, $d$ also divides the right side. – Erick Wong May 28 '13 at 18:51
up vote 3 down vote accepted

We are given that $d\mid x$ and $d\mid y$. So there are integers $m, n$ such that $$\;\;x = md, \quad \text{and}\quad y = nd$$

Then given $x = y + r \iff x - y = r$, we have $$x - y = md - nd = (m-n)d = r.$$

Hence $d\mid r$, as well, since $m, n$ are integers.

Then what can you say about $d$ with respect to the right-hand side: $$y + r = nd + (m-n)d = (n+m-n)d\quad?$$

share|cite|improve this answer
Nice! Now I see it clearly, thanks! – Math83 May 28 '13 at 19:08
You're welcome! – amWhy May 28 '13 at 19:08
@amWhy: Great feedback! =1 – Amzoti May 29 '13 at 0:40
It was a pretty good day for me, feedback-wise! That's the most rewarding part of answering questions ;-) – amWhy May 29 '13 at 0:41

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.