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

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

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.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.