3
$\begingroup$

I am currently reading through Donald Knuth's The Art of Computer Programming, and in it he gives a proof of Euclid's algorithm for finding the greatest common divisor of two number, $m$ and $n$.

In the proof, he defines $r$ as the remainder when diving $m$ by $n$ (in other words $r = m \mod n$) and writes $m = qn+r$ for some positive integer $q$.

From this he deduces that any number that divides both $m$ and $n$ must also divide $m-qn = r$. Similarly, he also says that any number that divides both $n$ and $r$ must also divide $qn+r = m$, with no further explanation.

I do not understand where these last two statements are coming from. Any help to guide me through the logic being employed here would be appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ Both statements are proved similarly and by little more than writing out what it means for $k$ to divide both $m$ and $n$. Give it a try, e.g $k$ divides $m$ means there exist an integer $a$ such that $m = ka$. Do the same for $n$ and plug into $m - qn = r$. $\endgroup$
    – hardmath
    Sep 25 at 5:23
  • $\begingroup$ Just combine 1) if $a \mid b$ then $a \mid bc$ for $\forall c$, and 2) if $a \mid b$ and $a \mid c$ then $a \mid b+c$. $\endgroup$
    – dxiv
    Sep 25 at 5:26
3
$\begingroup$

If $x$ is any number that divides $m$ and $n$, then we can write $m=k_1 x$ and $n=k_2 x$ for $k_1,k_2\in\mathbb{N}$. It follows that

\begin{align} m-qn &= k_1 x - qk_2 x\\ &= (k_1-qk_2)x \end{align}

so $m-qn$ is also divisible by $x$.

Similar reasoning can be applied to deduce that any number which divides $n$ and $r$ must also divide $qn+r$. If it helps, these results are actually special cases of a more general theorem:

If $x$ and $y$ are both divisible by $k$, then for any $a,b\in\mathbb{N}$, $ax+by$ is also divisible by $k$.

$\endgroup$
2
$\begingroup$

Do it once and never forget:

From this he deduces that any number that divides both m and n

So let $k$ be that number. Then $k|m$ so there is an integer $m'$ so that $m = km'$. And $k|n$ so there is an integer $n'$ so that $n = kn'$.

must also divide m−qn=r.

Now we have $m = qn +r$ so $m-qn = qn -qn +r$ and so $m-qn = r$ and $r =m-qn$.

Okay, so $r = m - qn$ but $m = m'k$ and $n =n'k$ so $r = m-qn = m'k - qn'k = k(m' + qn')$. And as $(m' + qn')$ is an integer, there is an integer, $(m'+qn')$, so that $k(m'+qn') =r$ so $k$ divides $r$.

... Anyway the text assumes that you are familiar with the result that if $k$ divides $a$ and $b$ then $k$ divides any linear combination, $wa \pm ub$, and you can recite and apply it in your sleep.

Similarly, he also says that any number that divides both n and r must also divide qn+r=m, with no further explanation.

Similar.

$m = qn +r$ so if $j$ divides $r$ and also divides $n$ then $j$ will divide and linear combination $un \pm wr$, including $qn + r$.

And to do it explicitly, if $j|n$ and $j|r$ there are integers $n''$ and $r''$ so that $n = jn''$ and $r= jr''$ and so $m = qn + r = qn''j + r''j = j(qn'' +r'')$ and $j|m$.

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