Multiples are closed under integral linear combinations My lecturer gave us the following side note when explaining the euclidean algorithm in class.

Eucledian Algorithm: Let $a$ and $b$ be natural numbers, then there are integers $m$ and $n$ such that $\gcd(a, b) = am + bn$
The implementation of the Euclidean
Algorithm consists of a sequence of repetitions
of the Division Algorithm with
the integers m and n being obtained
by unravelling this sequence of steps.
To appreciate why such an operation
identifies $\gcd(a, b)$, we may start with
the assumption that $a > b$ otherwise
$\gcd(a, b) = a$ (the case $a = b$) and there
is nothing to be done. When $a > b$
the Division Algorithm asserts that $a =
bq + r$ with $0  r < b.$ There are two
points to note.
a) Since $\gcd(a, b)$ divides $a$ and $b$ so
$\gcd(a, b)$ must also divide the remainder
$r.$ Therefore the greatest
common divisor of $a$ and $b$ is also
the greatest common divisor of $b$
and $r$, that is, $\gcd(a, b) = \gcd(b, r)$.
b) Since $b < a$ and $r < b$ the sequence
of applications of the Division Algorithm
generates a strictly decreasing
sequence of remainders terminating
with 0, but such that each remainder
is divisible by $\gcd(b, r)$. By definition,
the penultimate remainder is
therefore $\gcd(a, b)$.

I understand and can apply the algorithm, i.e. I can do the repeated division and find the gcd. But I still don't understand the part in bold above. Why can we just assume that?
When trying to prove the same for polynomials in a tutorial homework, I simply used a modified version of the part in bold as a lemma, specifically:

Any polynomial divisor of both $f(x)$ and $g(x)$ must also divide the remainder polynomial when $f(x)$ is divided by $g(x)$

and the tutor made no remark, so I'm assuming this is something which can be clearly seen but that I'm missing. Could anyone please break it down for me?
 A: Let $d=\gcd(a,b)$. You know $d$ divides both $a$ and $b$, and that means there are integers $k,l\in\mathbb{Z}$ such that $a=dk,b=dl$. And hence:
$r=a-bq=dk-dlq=d(k-lq)$
When $k-lq\in\mathbb{Z}$. So we got $d$ divides $r$. 
A: Key Idea $ $ Sets of $\rm\color{#c00}{integer}$ multiples (of $\,d)$ enjoy a fundamental linear structure - namely they are  closed under $\rm\color{#c00}{integral}$ linear combinations, i.e.
$\ \ $ if $\,\ \begin{align}a = \color{#c00}j\,d\\ b = \color{#c00}k\,d\end{align}\ \,$ are multiples of $\,d\,$ then so too is $\,ma\!+\!nb = \color{#c00}{(mj\!+\!nk)}d,\ $ for all integers $\,\color{#c00}{m,n}$
$ r = a\color{#c00}{-q}\,b\,$ is an $\rm\color{#c00}{integral}$ linear combination of multiples $\,a,b\,$ of $\,d\,$ so it too is a multiple of $\,d$.
Example $ $ If $\,ma+nb = 1\,$ then every common divisor of $a,b$ also divides $1,$ so $\,a,b\,$ are coprime.
The same is true for multiples in any ring $R\,$ if we replace the $\rm\color{#c00}{integral}$ multipliers $\,\color{#c00}{m,n}\,$ by arbitrary ring elements (e.g. polynomials in your second case), i.e. we use $R$-linear combinations.
This linear algebraic structure persists for multiples of many elements ("common multiples"). It is a prototypical example of an ideal $(R$-module) - a ubiquitous structure in number theory and algebra, so it is helpful to be familiar with this fundamental linear structure early in one's studies.

Alternatively: $\,\ d\mid a,b\Rightarrow (ja\!+\!kb\bmod d)= 0\!+\!0\,$ so $\,d\mid ja\!+\!kb\,$ by divisibility mod reduction. By congruences: $ 0\equiv a,b\Rightarrow\, ja\!+\!kb\equiv j(0)\!+\!k(0)\equiv 0\pmod{\!d}\,$ by congruence sum & product rules.
A: Well, if $d$ is the gcd of $a$ and $b$, and $a = qb+r$ where $r$ is the remainder, then $r= a - qb$. Thus $d$ divides the right-hand side and so $r$.
A: They are both the same:
If you ever have $k\mid M$ and $k\mid N$ then you have $k|aM \pm bN$ for any integers $a,b$.

Pf:  Do we really have to prove it?  $x\mid W \iff \frac Wx \in \mathbb
 Z$.  So $\frac {aM \pm bN}k = a\frac Mk \pm b\frac Nk$.  $k\mid M$ and
  $k\mid N$ so $\frac Mk, \frac NK$ are integers. So $\frac {aM \pm bN}k =
> a\frac Mk \pm b\frac Nk$ is an integer.  So $k|aM \pm bN$.

So $a = bq + r$ so $r = a - bq$ and $\gcd(a,b)|a$ and $\gcd(a,b)\mid b$ so $\gcd(a,b)\mid a - bq = r$.
That's it.
And for polynomials.
$f(x) = g(x)q(x) + r(x)$ then $r(x) = g(x)q(x) - f(x) = d(x) \left [\frac {g(x)}{d(x)} q(x) - \frac {f(x)}{d(x)} \right]$
