Year 12s: what will be the first way you research your future options? >>

dont 'get' the proof for the euclidean algorithm

username1398367

the proofs ive seen just dont click with me. ive heard that theres a geometric proof; do any of you know it?

(edited 9 years ago)

Reply 1

TeeEm

Original post by dire wolf

the proofs ive seen just dont click with me. ive heard that theres a geometric proof; do any of you know it?

you might need to change the title and include "proof"

Sorry I cannot help you with the proof ( I follow the algorithm )

Reply 2

Smaug123

Original post by dire wolf

the proofs ive seen just dont click with me. ive heard that theres a geometric proof; do any of you know it?

What do you not get? The proof of the fact that the Euclidean algorithm always terminates with the GCD of its input?

It's easy to see that the Euclid algorithm always terminates. Indeed, the numbers a,b get strictly smaller (well, to be picky, the sum a+b gets strictly smaller) at each step. Do you agree with that?

I prefer to think of the Euclidean algorithm as repeatedly subtracting the smaller number from the larger until one of the numbers becomes zero. Does that view help? It is clear from that that the output of the Euclidean algorithm is indeed a common factor of both input numbers. Do you agree with that?

Reply 3

username1398367

Original post by Smaug123

What do you not get? The proof of the fact that the Euclidean algorithm always terminates with the GCD of its input?

It's easy to see that the Euclid algorithm always terminates. Indeed, the numbers a,b get strictly smaller (well, to be picky, the sum a+b gets strictly smaller) at each step. Do you agree with that?

I prefer to think of the Euclidean algorithm as repeatedly subtracting the smaller number from the larger until one of the numbers becomes zero. Does that view help? It is clear from that that the output of the Euclidean algorithm is indeed a common factor of both input numbers. Do you agree with that?
this bit. i get why it goes to zero

Reply 4

Smaug123

Original post by dire wolf

this bit. i get why it goes to zero

Sorry, I don't really understand. You get that the algorithm does terminate, but not that it terminates at a common factor or that it terminates at the *highest* common factor?