algebra precalculus - Euclidean Algorithm Proof

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?

Answer

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