About Euclid's Algorithm proof 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.
 A: If $d$ divides both $a$ and $b$, say $a=da'$ and $b=db'$, then 
$$ r = a-qb=da'-qdb'=d\cdot(a'-qb').$$
A: 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.
A: $\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} $ 
