Re: GCD(0,0)

In article <ub8ar15vpkruhjloh52689tadvlcg5nl5g@xxxxxxx>,
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:
>>>>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.

I had originally written for my last post a paragraph about Bezout's
identity. However, in Bezout's identity, GCD(x,y) is the non-negative
generator of the ideal { ax + by : a and b integers }, so this added
very little to the post by Joe Silverman.

The usual Euclidean Algorithm applied to 0 and 0 would require dividing
0 by 0, and this would cause a problem. However, if we describe the
algorithm for non-negative x and y as

x = y q + r where r = 0 or r is the smallest positive integer possible
if r = 0, then y is the GCD
otherwise, x <- y, y <- r, repeat

This version is made so that GCD(0,x) = GCD(x,0) = x and GCD(0,0) = 0.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
.

Relevant Pages

  • Re: simple GCD question (but has me foxed)
    ... the GCD, ... Any integer that divides both x and y must also divide x-y, ... that both /sets/ of common divisors are exactly the same. ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... Any integer that divides both x and y must also divide x-y, ... following the "gcd is the largest common divisor" definition you ... that both /sets/ of common divisors are exactly the same. ... Don't really care at this point. ...
    (sci.math)
  • Re: quick question about divisibility
    ... Depends on your definition of "divides"; ... Generally GCD, LCM are dually definable as follows ... and efficient proofs of related identities, ... This is extracted from my prior post in this thread ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>>When it comes to common divisors, ... >>>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>When it comes to common divisors, ... >>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ... Sierpinski, Elementary Theory of Numbers, 1964 ...
    (sci.math)