Question. Let $a>b>1$ be integers. Consider the first two steps of the Euclidean algorithm for computing $\text{gcd}(a,b)$ $$a=q_1b+r_1,\quad b=q_2r_1+r_2.$$ Show that $r_2<2b$.
Now I know that of course $r_2$ must be less than $b$ as is the nature of remainders upon any division.
But where does the $2$ part come from? Why must it be that $r_2/2<b$?
Best Answer
$b=q_2(a-q_1b) +r_2$
$b=q_2a - q_2q_1b+r_2$
$b(1+q_1q_2) -q_2a=r_2 \implies b(1+q_1q_2) >r_2$
As $q_1, q_2$ both are greater than or equal to $1$ so $2b>r_2$