# Number of steps of Euclidean algorithm. why $r_i{_+}_2 < \frac{1}{2}r_i$?

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

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}$$.
• Sorry.. still not sure the last part why $r_{i+1} + r_{i+2} > 2r_{i+2}$? – zono Oct 28 '18 at 2:18
• @zono, because $r_{i+1} > r_{i+2}$. – lhf Oct 28 '18 at 10:44