2
$\begingroup$

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

  • 0
    @AD Spooky! Thanks for writing a full answer.2011-12-19

2 Answers 2

6

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.

3

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 (algebraic) structurally, the set $\rm\,D = d\, \mathbb Z\, $ of all multiples of $\rm\,d\,$ is closed under addition, and closed under multiplication by any integer, so it is closed under compositions of such operations, i.e. all integer-linear combinations of elements of $\rm\:D,\,$ e.g. $\rm\ m,n\in \mathbb Z,\ a,b\in D\ \Rightarrow\ m\,a+n\, b\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.