Re: GCD(0,0)

On Fri, 30 Dec 2005 06:13:20 -0600, David C. Ullrich
<ullrich@xxxxxxxxxxxxxxxx> wrote:

>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:
>>>>
>>>>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?
>>>
>>>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).

You do have to worry.

One of the things that is often done with the greatest common divisor
is _remove_ it by dividing it out.

Specifically

If gcd(a,b)=d then gcd(a/d,b/d)=1.

If d was allowed to be zero, the above result would need to have the
additional the assumption d<>0.

One way or the other, you do have to worry.

>Since that standard definition is in
>all other cases precisely equivalent to the one given above
>it seems like a very natural definition.

It has some arguments for it, some against. If it were that natural it
would probably would have been adopted as the standard. However, based
on the definition in most books, GCD(0,0) is undefined. That suggests
that what you think is the most natural is not in agreement with the
consensus view.

So if you think the standard definition is poorly chosen, fine, that's
your opinion. My opinion is the standard is just fine as it is, no
need to confuse things over something as trivial as GCD(0,0).

>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.

I agree that the PID scenario appears to argue in favor of GCD(0,0)=0.
However, as I pointed out in another reply, even Robert Gilmer, a
respected ring theorist, defines GCD for arbitrary commutative rings
with 1, but his definition requires the inputs to GCD to be nonzero
elements. He must have had a reason to preclude GCD(0,0).

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

Only if you allow inputs of 0,0.

Here's a link where you can test your claim:

<http://www.math.umn.edu/~garrett/crypto/a01/Euclid.html>

Here's another one:

<http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html>

>And yes, saying that that's what a simple algorithm
>returns is a reasonable reason for making a definition.

The algorithm comes after the definition, not before. There are many
algorithms that can give answers for inputs outside the domain of the
what the theory allows. Those results don't have to be taken so
seriously.

>>>
>>> ...
>>>
>>
>>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.

Resorting to personal attacks again?

Insisting that a standard definition is the wrong one is definitely
provocative. No big deal, everyone has the right to stir things up --
I cause such trouble all the time. But if you insist that your
definition is right, even though it conflicts with the consensus of
mainstream math, you should at least realize that you're in for a
fight.

>Suggesting that we consult standard texts is just silly, because everyone
>understands that the typical definition is going to leave
>GCD(0,0) undefined -

That's just it -- not everyone understands.

Besides, not every text does agree on this, although the overwhelming
majority do.

In fact, after seeing all the PID oriented arguments, suddenly I
wasn't so sure that my concept agreed with the standard, until I
checked a few sources.

>your string of posts following this one giving examples is a waste of space.

Now that's a silly objection. When arguing about definitions in
sci.math, it makes sense, and is quite commonly done, to post links,
references, quotes, to get a sense of what the standard actually is.

In some cases, there is no standard -- every author rolls their own.
In other cases, there's an overwhelming standard. It's important in
such an argument to know which situation you're in.

>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 a straw man argument. You won't find 5 such books, I doubt if
you can find even 1.

>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.

I suspect that the early users of complex numbers (up to and including
Gauss) were perfectly aware that they were potentially causing
trouble. They took the risk.

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

I would not define the GCD of 2 elements. I would define the GCD of 2
ideals. For ideals, you can have GCD(0,0)=0, and then simply note that
for the ring of integers, the GCD of ideals agrees with GCD of
elements, provided the elements are not all 0.

quasi
.

Relevant Pages

  • Re: GCD(0,0)
    ... >>>my point of view the G in GCD says it all. ... >>>unless there's a strong reason. ... >would probably would have been adopted as the standard. ... >>complex numbers then i is a square root of -1. ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>> standard, nearly universal, while for others there are competing ... Many abstract algebra and ring ... gcd is of course not the infimum with respect to the usual order ... >>| falls c ein Teiler von a und b ist, ...
    (sci.math)
  • Re: GCD(0,0)
    ... >> standard, nearly universal, while for others there are competing ... >> well as many that bar it. ... Many abstract algebra and ring ... >| If you unfold the definition if GCD you will see, that GCD ...
    (sci.math)
  • Re: GCD(0,0)
    ... There are terms that are so absolutely standard that decoding is easy ... I pointed out earlier that students generally don't have the right to ... it's often more convenient to think of the gcd as being ... >generalization and, sometimes they even get changed because it turns ...
    (sci.math)
  • Re: Problem about gcd (help me :) )
    ... for the gcd to make sense you need that ideals ... We can define a greatest common divisor ... in which finitely generated ideals are principal ideals. ... i.e. elements that are unit multiples ...
    (sci.math)
Loading