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

Lemma: Let $m$ and $n$ be positive integers with $m \leq n$. If $r$ is the remainder of dividing $n$ by $m$, then $(n,m) = (m,r)$.

The proof is given as follows:

We have by the division algorithm that $n = sm + r$ with $0 \leq r < m$. Suppose that $d = (n,m)$ and $e = (m, r)$. Since $r = n - sm$ and $d \mid n,$ $d \mid m$ we have $d \mid n - sm = r$.

The part I don't understand is how $d \mid n - sm = r$ is equivalent to $r = n - sm.$

It seems as if it is saying $n$ is the same as $d \mid n$.

share|cite|improve this question
LaTeX: \mid is better than |. – user2468 Aug 18 '12 at 5:56
up vote 2 down vote accepted

Since $d|n$ and $d|m$, we have $d|n-sm$. But $n-sm=r$, so $d|r$. "$d|n-sm=r$" is just a compressed way of writing all that. Does that answer your question?

share|cite|improve this answer
Yes it does, thank you. Sorry to all the other answerers, I can only tick one. – achacttn Aug 18 '12 at 6:04

Since $d|r$ and $d|m$, we have $d|(m,r)=e.$ On the other hand, $e|m$ and $e|r$, therefore $e|sm+r = n.$ Thus $e|(n,m)=d.$ So $d|e$ and $e|d$, implying $d=e.$

share|cite|improve this answer

In general if $d | n$ and $d | m$, then $d | (n - jm)$ for any integer $j$. To see this, let $n = ad$ and $m=bd$, then $(n-jm) = (ad -jbd) = d(a-jb)$ which is clearly divisible by $d$.

In your example, we know $d | n$, and $d | m$ (these are true because $d=(m,n)$). So $d | (n-sm)$ by the same rule.

share|cite|improve this answer

This line $d|n-sm=r$ is two separate sentences, which really could have been written on two lines. In other words, $d|n-sm$; and also, the right hand side of this statement $=r$.

share|cite|improve this answer

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.