Euclid's algorithm question

• Sep 2nd 2009, 12:34 AM
ordinalhigh
Euclid's algorithm question
Let \$\displaystyle b=r_0, r_1, r_2... \$ be the successive remainders in the Euclidean Algorithm applied to \$\displaystyle a\$ and \$\displaystyle b\$. Show that \$\displaystyle r_{i+2} \le r_i/2\$ for all \$\displaystyle i\$.

I'm thinking that this is proven by induction but I am stuck on the inductive step.
• Sep 2nd 2009, 01:21 AM
Taluivren
You don't need induction.
Suppose that \$\displaystyle r_{i+2}>r_i/2\$

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

we have \$\displaystyle r_i = q_{i+1}r_{i+1}+r_{i+2} > q_{i+1}r_{i+1} + r_i/2 \$
\$\displaystyle r_i/2 > q_{i+1}r_{i+1}\$ a contradiction.
• Sep 2nd 2009, 09:47 AM
ilovepurerubbish
can you explain why its a contradiction
• Sep 2nd 2009, 10:02 AM
Taluivren
Quote:

Originally Posted by ilovepurerubbish
can you explain why its a contradiction

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