Talk:Euclidean algorithm

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)

Everyone will realize instantly that the gcd of the two numbers you've ended up with is the common value, but it isn't obvious that this is also the gcd of the original numbers (rather than a multiple of the gcd).

Here's an idea for proving both halves (that the final number divides the gcd of the original numbers, and that the gcd of the original numbers divides the final number):

We have $a-b=c$. Note that any number which divides any two of these numbers must also divide the third number. In particular, any number which is a common divisor of a and b must divide c, and any number which is a common divisor of b and c must divide a. Therefore, any common divisor of (a,b) is a common divisor of (b,c), and any common divisor of (b,c) is a common divisor of (a,b). It follows that the set of common divisors of (a,b) is the same as the set of common divisors of (b,c), and therefore that the greatest common divisor of (a,b) is also the greatest common divisor of (b,c).

--Catherine Woodgold 18:22, 13 May 2007 (CDT)

That argument is the straightforward one. I think how Euclid did it is probably found here. I'll look that over more closely later. Michael Hardy 18:55, 13 May 2007 (CDT)

Some of my reasoning in my first comment above was wrong. The process stops when one of the numbers is zero. You never get to a point where both of the numbers are zero, so it doesn't matter that all numbers divide zero. --Catherine Woodgold 07:55, 14 May 2007 (CDT)

The "full-fledged" Euclidean algorithm includes (for essentially no extra work) more information. If c = gcd(a,b), then there exist intergers n and m (not necessarily positive!) such that c = ma + nb. In fact, the only numbers which can be written in the form ma + nb are divisible by c. In particular, you can write 1 = ma + nb if and only if a and b are relatively prime. The Euclidean algorithm not only produces c, but it also produces m and n with no additional work. I think this version should be presented.Holger Kley 11:52, 25 May 2007 (CDT)