Euclid's algorithm question

**ordinalhigh** · September 2nd 2009, 12: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** · September 2nd 2009, 01: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** · September 2nd 2009, 09:47 AM

can you explain why its a contradiction

**Taluivren** · September 2nd 2009, 10:02 AM

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

Thread: Euclid's algorithm question

LinkBack

Thread Tools

Display

Euclid's algorithm question

Similar Math Help Forum Discussions

Euclid Algorithm

Help with Euclid's algorithm question

Euclid's Algorithm

Another GCD using Euclid's Algorithm

Euclid's algorithm

Search Tags