Re: GCD(0,0)

On Thu, 29 Dec 2005 20:58:08 -0500, quasi <quasi@xxxxxxxx> wrote:

>On 29 Dec 2005 19:59:26 -0500, hrubin@xxxxxxxxxxxxxxxxxxxx (Herman
>Rubin) wrote:
>
>>In article <1135888209.029280.145500@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
>>Leroy Quet <qqquet@xxxxxxxxxxxxxx> wrote:
>>>I notice that these math-controversy threads often get massive
>>>numbers of replies.
>>>(While more serious math posts and my games, for example,
>>>hardly ever get any replies.)
>>>So I will post this troll-bait flame-bait message to sci.math
>>>because I always wanted to start one of those huge threads.
>>>:)
>>
>>>For n = any positive integer, it is known that
>>
>>>GCD(n,n) = n
>>
>>>and
>>
>>>GCD(0,n) = n.
>>
>>>(GCD is Greatest Common Divisor, of course.)
>>
>>>But what is, if there is any defined value,
>>
>>>GCD(0,0)?
>>
>>>It certainly isn't 0 (which would fit the pattern above if
>>>n=0), is it?
>>>I would think that infinity would work as well as anything.
>>
>>>Or is GCD(0,0) simply undefined, like 0/0?
>>
>>
>>>thanks, (half seriously, oh well, 3/4 seriously)
>>>Leroy Quet
>>
>>When it comes to common divisors, since everything
>>divides 0, and otherwise an integer never divides
>>a smaller integer, for this purpose, 0 is the
>>greatest common divisor of 0 and 0.
>
>You're justifying an exception to the name GCD by pointing out that 0
>has other special properties. Sure, we could define gcd(0,0)=0 or we
>could leave it undefined. You can make the case for either one. From
>my point of view the G in GCD says it all. No need to confuse things
>unless there's a strong reason.

A strong reason to want a definition of GCD(0,0) is so we
don't have to worry about whether x and y are both 0 when
we mention GCD(0,0). Since that standard definition is in
all other cases precisely equivalent to the one given above
it seems like a very natural definition.

To put the same point another way: Read the rest of the
thread, in particular the post by JoeS. The notion of
GCD generalizes in a perfectly natural way to an
arbitrary PID. But the definition that works in a PID
is equivalent to the definition above, and gives
GCD(0,0) = 0.

Another justification that I don't see mentioned yet:
The euclidean algorithm gives GCD(0,0) = 0.

And yes, saying that that's what a simple algorithm
returns is a reasonable reason for making a definition.
For example, say S is a finite set of reals, and define
sum(S) and prod(S) to be the sum and product of all
the elements of S, respectively. What should these
be if S is empty? You can't add no numbers or multiply
no numbers; nonetheless it's clear that sum(S) should
be 0 and prod(S) should be 1 if S is empty. Why?
One reason being that the following algorithm
returns sum(S) when S is nonempty (and similarly
for prod(S)):

def sum(S):
temp = 0
for x in S:
temp = temp + s
return temp

>One way or the other, it's an exception -- either it's not defined so
>that's an exception, or it is defined, but in an exceptional way. So
>in a sense the choice is arbitrary, but there are tradeoffs to be
>weighed. However, you don't get to decide the issue yourself if
>there's already a consensus. Let's check respected texts on Number
>Theory and see what side of this argument they take, If most or
>perhaps nearly all of them define gcd(0,0) undefined, you are just
>causing trouble to insist otherwise.

Saying he's "causing trouble" is obnoxious. Suggesting that
we consult standard texts is just silly, because everyone
understands that the typical definition is going to leave
GCD(0,0) undefined - your string of posts following this
one giving examples is a waste of space.

It's as though someone asked what the square root of -1
was. Someone replies there's no such thing. Someone else
replies that it depends on the context; if we're allowing
complex numbers then i is a square root of -1. Now you
say let's consult some respected texts, and you cite
5 algebra books that say that -1 has no square root.
That's silly, for two reasons: (i) it's not necessary,
since we all know that it says in those books that
-1 has no square root, (ii) it's pointless, since the
fact that those books say that -1 has no square root
does not imply that complex numbers don't exist, or
that they're of no interest, just invented to cause
trouble.

How would _you_ define the GCD of two element of a PID?

>> The ordering is that of divisibility.
>
>So you proclaim.
>
>>This also holds for least common multiple.
>
>LCM doesn't need to be undefined.
>
>0 is multiple of 0, so LCM(0,0)=0 is just fine.
>
>0 is not a divisor of 0.
>
>If you don't believe it, let's see what the books have to say.
>
>quasi


************************

David C. Ullrich
.

Relevant Pages

  • Re: Yads
    ... Yads' posts aren't the problem, it's the replies to them so unless you also ... killfile everyone who replies to them you're wasting your time. ... Remember Christ is the reason for the season. ...
    (uk.media.tv.sf.drwho)
  • Re: OT: Agent 3.0
    ... >>> On the rare occasions when I only want to see replies to my posts, ... >>> have fired up OE for this reason. ...
    (uk.rec.motorcycles)
  • Re: Cant see my posts
    ... If anyone finds a cure to this "can't read own posts" problem, I sure would be interested in the solution. ... I don't know if lately the replies simply are not being posted as rapidly as before or what the problem is. ... here is a perfect example using Google groups. ... > I quit using motzarellla.org for these groups for a similar reason. ...
    (microsoft.public.windows.vista.general)
  • Re: more on the history of "energy efficiency research" - ie. calories
    ... There are no replies to his posts because, ... pseudo-scientific references, TC's posts are founded on firm scientific ... There is no reason for replies because there is no reason for ...
    (sci.med.nutrition)
  • Re: OT Some really bad music (I wonder who funded it?)
    ... > Oh tee, please, gentlemen! ... For some reason, the OT has dropped off some recent ... posts, even though they were replies in an OT thread. ...
    (rec.music.classical.recordings)