Talk:Euclidean algorithm

Article Checklist for "Euclidean algorithm"

Workgroup category or categories	Mathematics Workgroup [Categories OK]
Article status	Developing article: beyond a stub, but incomplete
Underlinked article?	No
Basic cleanup done?	Yes
Checklist last edited by	Catherine Woodgold

To learn how to fill out this checklist, please see CZ:The Article Checklist.

---

It says "Since one cannot go on getting smaller and smaller positive integers forever, one must reach a point where one of the two is 0." This seems to imply that 0 is a positive integer (or the proof isn't quite rigourous or something; if 0 is allowed, maybe other things that are not positive integers are allowed so one can't use well-ordering? Just a minor point that needs to be cleaned up in the wording, though I don't immediately see a good way to do it.)

Instead of saying that it stops when one number is 0, we could say that it's all positive integers and that it stops when the two are equal. (Subtracting two unequal positive integers always supplies a positive integer). There is actually another problem if zero is allowed: all numbers divide zero. So you have to show that you reach a point where one of the numbers is zero but the other number is not also zero, since (0, 0) for the two numbers wouldn't tell you much. Stopping when the two are equal avoids the problem of mentioning zero. Not that it's that hard to argue that just before you got zero you must have gotten a last non-zero positive integer.

Or maybe all that needs to be added is a statement that all the numbers are either positive integers or zero (how do we know this? -- another tiny wrinkle. When the two are equal we aren't subtracting the smaller from the larger since there is no smaller or larger. Stopping when the two are equal would solve that wrinkle, too.) I wonder how Euclid did it.

Another problem: It is implied here but not stated (and it is true, and is stated on the Greatest common divisor page) that the last number found before 0 is the gcd (rather than being a larger number divisible by the gcd), but no proof is given for this. I think there's a simple inductive proof working backwards from the end of the algorithm. --Catherine Woodgold 08:36, 13 May 2007 (CDT)

---

We could just say "nonnegative" instead of "positive" and then of course well-ordering still applies. The advantage to stopping when they're equal is that then everyone will realize instantly that the gcd is the common value. Michael Hardy 17:32, 13 May 2007 (CDT)