# Confusion for Proof of GCD Theorem?

I'm having some trouble understanding a part of a theorem that states that the gcd between two integers exists and is unique. First it state the Euclidean Algorithm for positive integers, that for positive integers $a$ and $b$, \begin{align} a & = bq_1 + r_1 \\ b & = r_1q_2 + r_2 \\ r_1 & = r_2q_3 + r_3 \end{align} As long as the remainders aren't zero

And so on and so forth. Then it states the fact that $b > r_1 > r_2 > r_3 >\cdots>0$

Then it says, using induction, that $$0 \le r_i \le b - i.$$

Where did that $b - i$ come from? What does it mean? How is this inequality true?

## 1 Answer

$r_1<b$, since $r_1$ is the remainder upon dividing by $b$. Thus $r_1\le b-1$, since we are dealing with integers here. Next, $r_{k+1}<r_k$, and hence $r_{k+1}\le r_k-1$ for the same reason. From this, the conclusion is immediate by induction.

• Wow. Thank you so much. I didn't realize that for integers, if a < b implies a <= b - 1. Mind blown haha – tralaman Apr 3 '16 at 19:19