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.
Follow Math Help Forum on Facebook and Google+
You don't need induction. Suppose that we have a contradiction.
can you explain why its a contradiction
Originally Posted by ilovepurerubbish can you explain why its a contradiction It contradicts the choice of . Do you see that we could as well take instead of (which contradicts the fact that we always take maximal possible 's)?
View Tag Cloud