Euclid's algorithm question

ordinalhigh · #1 $Old$ September 2nd, 2009, 01:34 AM

Let $b=r_0, r_1, r_2...$ be the successive remainders in the Euclidean Algorithm applied to $a$ and $b$ . Show that $r_{i+2} \le r_i/2$ for all $i$ .

I'm thinking that this is proven by induction but I am stuck on the inductive step.

Taluivren · #2 $Old$ September 2nd, 2009, 02:21 AM

You don't need induction.
Suppose that $r_{i+2}>r_i/2$

$r_{i-1} = q_ir_i+r_{i+1}$
$r_i = q_{i+1}r_{i+1}+r_{i+2}$

we have $r_i = q_{i+1}r_{i+1}+r_{i+2} > q_{i+1}r_{i+1} + r_i/2$
$r_i/2 > q_{i+1}r_{i+1}$ a contradiction.

ilovepurerubbish · #3 $Old$ September 2nd, 2009, 10:47 AM

can you explain why its a contradiction

Taluivren · #4 $Old$ September 2nd, 2009, 11:02 AM

Quote:

Originally Posted by ilovepurerubbish $View Post$

can you explain why its a contradiction

It contradicts the choice of $q_{i+1}$ . Do you see that we could as well take $q_{i+1}+1$ instead of $q_{i+1}$ (which contradicts the fact that we always take maximal possible $q$ 's)?