I'm reading "Friendly Introduction to Number Theory". Now I'm working on Number of steps of Euclidean algorithm Exercises 5.3 on P35.
5.3. Let b = r0, r1, r2, . . . be the successive remainders in the Euclidean algorithm applied
to a and b. Show that after every two steps, the remainder is reduced by at least one half.
In other words, verify that
$r_i{_+}_2 < \frac{1}{2}r_i$ for every i = 0, 1, 2, . . . .
https://www.math.brown.edu/~jhs/frintch1ch6.pdf
I confirmed the above equation worked. But I don't understand where $1/2$ came from? Can you give me a hint?
$22x + 60y = gcd(22, 60)$
$60 = 2 * 22 + 16$
$22 = 1 * 16 + 6$
$16 = 2 * 6 + 4$
$6 = 1 * 4 + 2$
$4 = 2 * 2 + 0$
Update 1
@lhf gave me the comment but I can't understand the step (5). Why 2$r_{i+2}$ ?
(1) $r_i = r_{i+1} q_{i+2} + r_{i+2}$
(2) with $r_{i+2} < r_{i+1}$.
(3) Since $r_{i+1} < r_{i}$, we have $q_{i+2} \ge 1$,
(4) and so $r_i = r_{i+1} q_{i+2} + r_{i+2} \ge r_{i+1} + r_{i+2}$.
(5) $r_{i+1} + r_{i+2} > 2r_{i+2}$
//
$22x + 60y = gcd(22, 60)$ // a=60, b=22
$60 = 2 * 22 + 16$ // $a = 2*b + r_i$
$22 = 1 * 16 + 6$ // $b = 1*r_i + r_i{_+}_1$
$16 = 2 * 6 + 4$ // $r_i = 2*r_i{_+}_1 + r_i{_+}_2$
$6 = 1 * 4 + 2$
$4 = 2 * 2 + 0$
Best Answer
We have $ r_i = r_{i+1} q_{i+2} + r_{i+2} $ with $r_{i+2} < r_{i+1}$.
Since $r_{i+1} < r_{i}$, we have $q_{i+2} \ge 1$, and so $ r_i = r_{i+1} q_{i+2} + r_{i+2} \ge r_{i+1} + r_{i+2} > 2r_{i+2} $.