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
    @DylanMoreland Whoops you even used my letters.. :)2011-12-19
  • 0
    @AD Spooky! Thanks for writing a full answer.2011-12-19

2 Answers 2

5

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\qquad 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 subtraction, and closed under multiplication by any integer. Hence it is closed under compositions of such operations, which amount to integer-linear combinations of elements of $\rm\:D\:.\:$ In particular we have $\rm\ m,n\in \mathbb Z,\ a,b\in D\ \Rightarrow\ m\ a+n\ b\in D\:.\:$ When 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.