In the book Elementary Number Theory: Primes, Congruences and Secrets written by William Stein, which can be found at http://wstein.org/ent/, Stein proves the following at page 6/lemma 1.1.17:
Lemma $\ $ For any integers $a, b, n,$ we have $\, \gcd(an, bn) = |n|\gcd(a, b)$
Proof $\ $ We step through Euclid's algorithm for $\gcd(an, bn)$ and note that at every step the equation is the equation from Euclid's algorithm for $\gcd(a, b)$ but multiplied through by $n.$ For simplicity, assume that both $a$ and $b$ are positive. We will prove the lemma by induction on $a + b$. The statement is true in the base case when $a + b \le 2$, since then $a = b = 1$. Now assume $a, b$ are arbitrary with $a \ge b$. Let $q$ and $r$ be such that $a = bq + r$ and $0 \le r < b$. Then by Lemmas 1.1.9-1.1.10, we have $\gcd(a, b) = \gcd(b, r)$. Multiplying $a = bq + r$ by $n$ we see that $an = bnq + rn$, so $\gcd(an, bn) = \gcd(bn, rn)$. Then
$$b + r = b + (a - bq) = a - b(q - 1) \le a < a + b,$$
so by induction $\gcd(bn, rn) = |n|\gcd(b, r)$. Since $\gcd(b, r) = \gcd(a, b)$, this proves the lemma.
My main question concerning this proof is that i have troubles following how $b + r < a + b$ leads to the fact that $\gcd(bn, rn) = |n| \gcd(b, r).$
I think that my troubles comprehending this proof is related to my basic understanding of mathematical induction, I never even knew what it was before stumbling upon this proof. My current understanding of induction is that you prove your statement for a base case, $a + b = 2,$ then you prove that if the statement is true for any one natural number then it is true for the next. However i do not understand how that principle is used in this proof, any explanation is greatly appriciated.