Clarification on the proof for the Euclidean algorithm

Question

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$.

Answer 1

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?

Answer 2

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.$

Answer 3

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.

Answer 4

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$.