gcd 0 0 = 0
Alan Bawden
Alan@LCS.MIT.EDU
Thu, 13 Dec 2001 22:55:31 -0500 (EST)
From: "S.D.Mechveliani" <mechvel@math.botik.ru>
Date: Thu, 13 Dec 2001 12:53:32 +0300
Further, the definintion
> gcd(x, y) to be the smallest
> z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}
is not natural. In particular, how does it generalize to gcd X Y
for polynomials in X, Y with rational coefficients?
Well, that -is- the way gcd is defined in the commutative algebra textbook
I used in graduate school -- I just specialized the definition for the case
of the ring of integers, and so I didn't mention that Z was a principle
ideal domain. Polynomials in two variables aren't a PID, so yes, you'd
have to restore some things I left out. When I said my definition was
"general" I suppose I should have anticipated someone would generalize in a
way I hadn't intended... (Actually, that definition doesn't even
generalize exactly to the Gaussian Integers, where "z >= 0" would have to
be replaced by some specification of a region of the complex plane.)
...
Probably, the best specification would be
gcd n m :: Integer = if n == 0 && m == 0 then 0
else
greatest integer that divides both n and m
Fortunately, we all seem to agree on what the actual definition should be.
I did make a mistake in my previous message. I said that it was nice that
gcd(0, x) = x for all x. I should have said: gcd(0, x) = abs(x).