# Math Help - Euclid's algorithm question

1. ## Euclid's algorithm question

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.

2. 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.

3. can you explain why its a contradiction

4. Originally Posted by ilovepurerubbish
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)?