1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! Can you give me some time to think about it? $\endgroup$ – zono Oct 27 '18 at 15:02
  • $\begingroup$ Sorry.. still not sure the last part why $r_{i+1} + r_{i+2} > 2r_{i+2}$? $\endgroup$ – zono Oct 28 '18 at 2:18
  • 1
    $\begingroup$ @zono, because $r_{i+1} > r_{i+2}$. $\endgroup$ – lhf Oct 28 '18 at 10:44
  • $\begingroup$ I got it finally. Thank you so much. $\endgroup$ – zono Oct 28 '18 at 14:42

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.