Re: GCD(0,0)

Leroy Quet <qqquet@xxxxxxxxxxxxxx> wrote:
>[...]
> 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?

That is a common misconception about the meaning of "greatest"
in the phrase "_greatest_ common divisor".

The actual order on the natural numbers which is meant here, is
not the usual one but the _divisibility_ order |.

you can check easily that is reflexive and transitive
( i.e., m|m and l|m & m|n ==> l|n ). It is also
antisymmetric as long as only natural numbers are considered.

If you unfold the definition if GCD you will see, that GCD(m,n)
is just the infimum of m and n with respect to order |.
(also LCM(m,n) is the supremum of m an m).
Hence GCD(m,m)=m and in particular GCD(0,0).

If you consider all integers, the relation | is not antisymmetric
any more. But you still have the notion of "a greatest element",
and _a_ GCD(i,k) is _a_ greatest element of the set of common divisors
of i and k.

That the _usual_ order on the naturals is not really important for
the concept of GCD becomes clear when more general Rings (i.e. k[X])
are considered.

Marc
.

Relevant Pages

  • Re: GCD(0,0)
    ... >>my point of view the G in GCD says it all. ... >>unless there's a strong reason. ... One of the things that is often done with the greatest common divisor ... would probably would have been adopted as the standard. ...
    (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)
  • Re: LCM, GCD defined for negative numbers?
    ... Are the concepts of Lowest Common Multiple and Greatest Common Divisor ... the gcd of any two integers x and y is the ... lcm= 0 for all integers n, and if x and y are both nonzero, then ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... the GCD, ... common divisor" of m and n is the largest integer dividing both m and n). ... Any integer that divides both x and y must also divide x-y, ... but as denoting the partial ordering "x divides y" you intend by ...
    (sci.math)
  • How to write a small graceful gcd function?
    ... /*The Greatest Common Divisor, GCD for short, of two positive integers ... can be computed with Euclid's division algorithm. ... If the remainder c is zero, b is the greatest common divisor. ...
    (comp.lang.c)