# Divisor of $m$ and $n$ divides $m - qn$ (in proof of Euclidean algorithm)

In Knuth's book "The Art Of Computer Programming Vol.1" there is a description about Euclid's algorithm to find the greatest common divisor of m and n.

And there is a phrase.

$m = qn+r$. If $r = 0$, then $m$ is a multiple of $n$, and clearly in such a case $n$ is the greatest common divisor of $m$ and $n$. If $r \neq 0$, note that any number which divides both $m$ and $n$ must divide $m -qn =r$ , and any number which divides both $n$ and $r$ must divide $qn+r =m$.

I don't understand why any divisor of $m$ and $n$ must divide $m-qn =r$.

• @DylanMoreland Whoops you even used my letters.. :) – AD. Dec 19 '11 at 16:28
• @AD Spooky! Thanks for writing a full answer. – Dylan Moreland Dec 19 '11 at 17:06

For the last line in your post: Suppose $d$ divide both $m$ and $n$, this means that there are integers $a,b$ such that $m=ad$ and $n=bd$ and then $$r= m-qn= ad -qbd=(a-qb)d$$ that is $d$ divides $r$ too.
Hint $$\rm\quad q\:,\ \dfrac{m}d,\ \dfrac{n}d\ \in\ \mathbb Z\ \ \Rightarrow\ \ \dfrac{m - q\ n}{d}\ =\ \dfrac{m}d\ -\ q\ \dfrac{n}d\ \in\ \mathbb Z$$
Said more structurally, the set $$\rm\,D = d\:\! \mathbb Z\,$$ of all multiples of $$\rm\,d\,$$ is closed under addition, and closed under scalings (multiplication by an integer), so it is closed under compositions of such operations, i.e. all integer-linear combinations of elements of $$\rm\,D,\,$$ so $$\rm\ m,n\in \mathbb Z,\ a,b\in D\ \Rightarrow\ ma+nb\in D.\,$$ If you study ring theory you will learn that this is a prototype of a fundamental ubiquitous algebraic structure known as an ideal or $$\rm\:R$$-module (a ring-theoretic analog of a vector space)