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.

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|improve this question
3  
LaTeX: \mid is better than |. –  user2468 Aug 18 '12 at 5:56
add comment

4 Answers 4

up vote 1 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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.