Let be the successive remainders in the Euclidean Algorithm applied to and . Show that for all .

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

Printable View

- Sep 2nd 2009, 01:34 AMordinalhighEuclid's algorithm question
Let be the successive remainders in the Euclidean Algorithm applied to and . Show that for all .

I'm thinking that this is proven by induction but I am stuck on the inductive step. - Sep 2nd 2009, 02:21 AMTaluivren
You don't need induction.

Suppose that

we have

a contradiction. - Sep 2nd 2009, 10:47 AMilovepurerubbish
can you explain why its a contradiction

- Sep 2nd 2009, 11:02 AMTaluivren