Why $\gcd(qb+r,b)=\gcd(b,r)$?

Hint $\rm\, $ If $\rm\ d\mid \color{#c00}b\ $ then $\rm\ d\ |\ q \color{#c00}b + r \iff d\ |\ r.\, $ Therefore $\rm\ \{b,\:qb+r\}\ $ and $\rm\ \{b,\: r\}\ $ have the same set $\,\rm S\,$ of common divisors $\rm\:d,\:$ so they have the same greatest common divisor $\rm(= \max S)$.

Said $\rm\bmod d\!:\: $ if $\rm\ \color{#c00}{b\equiv 0}\ $ then $\rm\ q\color{#c00}b+r\equiv 0 \iff r\equiv 0$

So $\,\rm \bbox[5px,border:1px solid #c00]{\gcd(a,b) = \gcd(b,a\bmod b)}\,$ where $\rm \,a = qb+r,\ r = a\bmod b,\,$ by the division algorithm, which is the descent step in the Euclidean algorithm for the gcd.

Remark $ $ The result holds true because $\rm\:\mathbb Z\:$ forms a subring of its fraction field $\rm\:\mathbb Q.\,$ More generally, given any subring $\rm\:Z\:$ of a field $\rm\:F\:$ we define divisibility relative to $\rm\ Z\ $ by $\rm\ x\mid y \iff y/x\in Z.\,$ The above proof still works, since if $\rm\ q,\ b/d\ \in Z\, $ then $\rm\, q\,(b/d) + r/d\in Z\iff r/d\in Z.\:$ Thus the common divisibility laws follow from the fact that (sub)rings are closed under subtraction and multiplication (subring test). Being so closed, $\rm\:Z\:$ serves as a ring of "integers" for divisibility tests.

For example, to focus on the prime $2$ we can ignore all odd primes and define a divisibility relation so that $\rm\ m\ |\ n\ $ if the power of $2$ in $\rm\:m\:$ is $\le$ that in $\rm\:n\:$ or, equivalently if $\rm\ n/m\ $ has odd denominator in lowest terms. The set of all such fractions forms a ring $\rm\:Z\:$ of $2$-integral fractions. Moreover, this ring enjoys parity, so arguments based upon even/odd arithmetic go through. Similar ideas lead to powerful local-global techniques of reducing divisibility problems from complicated "global" rings to simpler "local" rings, where divisibility is decided by simply comparing powers of a prime.

If $d$ is a divisor of $a$ and of $b$, then $$ \begin{align} a & = dn, \\ b & = dm. \end{align} $$ So $$a-b= dn-dm=d(n-m)= (d\cdot\text{something}).$$ So $d$ is a divisor of $a-b$.

Thus: All divisors that $a$ and $b$ have in common are divisors of $a-b$.

If $d$ is a divisor of $a$ and of $a-b$, then $$ \begin{align} a & = dn, \\ a-b & = d\ell. \end{align} $$ So $$ b=a-(a-b)=dn-d\ell=(d\cdot\text{something}). $$ So $d$ is a divisor of $b$.

Thus: All divisors that $a$ and $a-b$ have in common are divisors of $b$.

Therefore, the set of all common divisors of $a$ and $b$ is the same as the set of all common divisors of $a$ and $a-b$.

Subtracting one member of a pair from the other never alters the set of all common divisors; therefore it never alters the $\gcd$.

You can show that for any integer $d$, we have $d\; |\; a$ and $d\; |\; b$ if and only if $d\; |\; b$ and $d\; |\; r$. In other words, $a$ and $b$ have exactly the same common divisors as $b$ and $r$. Thus $\gcd(a,b)$ is the same as $\gcd(b,r)$.