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.
Best Answer
If $d$ divides both $a$ and $b$, say $a=da'$ and $b=db'$, then $$ r = a-qb=da'-qdb'=d\cdot(a'-qb').$$