# Euclid's algorithm question

• September 2nd 2009, 12:34 AM
ordinalhigh
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.
• September 2nd 2009, 01:21 AM
Taluivren
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.
• September 2nd 2009, 09:47 AM
ilovepurerubbish
can you explain why its a contradiction
• September 2nd 2009, 10:02 AM
Taluivren
Quote:

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)?