4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.