# Why must this divisibility statement be true?

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.

• 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$. Sep 25 at 5:23
• 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$.
– dxiv
Sep 25 at 5:26

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

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