Reading Lecture 5 here I found this proof for the long division remainder-based Euclid's GCD algorithm (page 20):

Given any two non-negative integers $$a$$ and $$b$$, we can obviously write $$a = q·b +r$$ for some non-negative quotient integer $$q$$ and some non-negative remainder integer $$r$$.

It follows directly from the form $$a = q·b + r$$ that every common divisor of $$a$$ and $$b$$ must also divide the remainder $$r$$.

[...]

Why is it that every common divisor of $$a$$ and $$b$$ must also divide the remainder $$r$$? I can't understand it.

• BTW, that proof is awfully gappy. "We can obviously write" follows by chosing $q=0$ and $r=a$, which does not help us in any wy for the algorithm. The crucial step is that $0\le r<b$ can be quaranteed! This is an important property of the ring of integers that may not apply to other rings. – Hagen von Eitzen Apr 6 '13 at 16:37

If $d$ divides both $a$ and $b$, say $a=da'$ and $b=db'$, then $$r = a-qb=da'-qdb'=d\cdot(a'-qb').$$

• Simple, nice. It makes sense. Thanks :) – Alicia Apr 6 '13 at 17:10

It $t$ divides $a$ and $b$, then $t$ divides $a-qb$. But $a-qb=r$.

If you need full detail, let $a=ta'$ and $b=tb'$. Then $a-qb=t(a'-qb')$. So $t$ divides $a-qb$.

Remark: The calculation above holds whenever there is a decent notion of divisibility.

One should not underestimate the difficulty of the assertion that if $b$ is positive, there exist $q$ and $r$ such that $a=qb+r$ and $0\le r\le b-1$. True, it follows fairly quickly from the fact that every non-empty set of non-negative integers has a smallest element, or, equivalently, by induction.

The result about $q$ and $r$ generalizes nicely in only a restricted number of cases. For details, google Euclidean domain.

$\rm\begin{array}{rrl}{\bf Hint}\quad d\mid a,b\!\!\!\! &\Rightarrow&\!\!\!\rm a\equiv \,\color{#C00}0,\ b\equiv \,\color{#0A0}0\ \ \,(mod\ d)\\ &\Rightarrow&\!\!\!\! \begin{eqnarray}\rm r &\,=\:&\rm a-q\cdot b\\ &\,\equiv\:&\rm \color{#C00}0 -q\cdot \color{#0A0}0\,\equiv\, 0\ \ (mod\ d)\end{eqnarray}\\ &\Rightarrow&\rm\!\!\! d\mid r \end{array}$