Irrational GCD

[Alan Bawden <ALAN at SCRC-TENEX>]

    Date: Friday, 28 December 1984, 01:28-PST
    From: Bill Gosper <rwg at SPA-NIMBUS>
        Date: Wednesday, 19 December 1984, 23:45-EST
        From: David C. Plummer in disguise <DCP at SCRC-QUABBIN>
	    [(GCD 1\4 1\3) errs.]
	    . . .

	    BTW, the correct answer is 1\12.

        Not as far as ZL is concerned.  Nor CL for that matter.

    Ouch!  They must have been jet-lagged at those CL meetings.  As
    Schroeppel pointed out several millenia back,

    (GCD A\B C\D) = (GCD A C)/(LCM B D),

    assuming args are in lowest terms.  MACSYMA has long known this.

You know Gosper, I had always assumed that people who proposed to extend
GCD to the rationals were just confused about just what GCD really was, so
I was quite surprised to hear that this was an idea endorsed by Schroeppel.
So I thought about it for a while...

In what sense must the GCD of 1/3 and 1/4 be 1/12?  Suppose I pick some
subring of Q that contains both 1/3 and 1/4 and I look at the ideal
generated by 1/3 and 1/4.  Certainly that ideal is the same as the ideal
generated by 1/12, and in general the formula you give above will always
yeild such a generator, but there are many other elements in the ring that
generate that ideal.  In fact, since 1/12 is a unit in any subring of Q,
that ideal must be generated by 1, so why not say GCD(1/3,1/4)=1?  What is
the additional constraint you impose that requires 1/12?

Well, suppose that instead of thinking about GCD as defined in terms of
generators of ideals in subrings of Q, we think about GCD as defined in
terms of generators of Z-modules contained in Q.  In that case, the formula
above gives the unique (modulo sign) generator of the module generated by
the arguments to GCD.  But that seems somewhat arbitrary; suppose I was
working with some ring other than Z, call it A, and I wanted to play with
A-modules contained in Q?  No problem!  Although the formula can't always
give you a unique generator, it will give you -one- of the generators,
which is certainly the best you can ask for.

Summary:  I'm convinced.  This really is the right way to extend GCD to the
rational numbers if you are going to do it at all.  (Since my suggestions
that GCD, NUMERATOR and DENOMINATOR be extended in the -only- possible way to
the complex integers were ignored, I have little hope that Common Lisp will
adopt the idea, however.)

    But the absoLULU is further down page 202 of the CL book:

    "Mathematically, (lcm) should return infinity."  This is so wildly
    absurd that I can't even guess the fallacy that led to it.  It should
    simply be 1.

It is clearly a result of taking the identity
 (LCM ...) = (/ (ABS (* ...)) (GCD ...))
too seriously.