Re: GCD(0,0)


Rob Johnson wrote:
> 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

As David Ulrich says, it's quite reasonable to define something as the
output of an algorithm. (One has to prove that the algorithm
terminates, of course.) In general a ring R is "Euclidean" if it has a
Euclidean algorithm, which means that it has a size function

s : R ---> (nonnegative real numbers)

satisfying certain properties. It's easy to show that a Euclidean ring
is a PID and that the output from the Euclidean algorithm is a
generator for the ideal generated by a and b. But there are rings that
are PIDs, but are not Euclidean. So in terms of generalizing the notion
of GCD, using the Euclidean algorithm seems like a halfway step. OTOH,
I certainly agree that it provides an instructive way to think about
what it means to generalize a concept.

.

Relevant Pages

  • Re: euclidean algorithm over Q[i]
    ... apart from the final value for the gcd. ... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... advantage to using 'pseudo division' to avoid large ...
    (sci.math.symbolic)
  • Re: how to rotate an array
    ... You can easily find the explanation of Euclidean algorithm on the Internet. ... gcd of original a,b values. ... > loops through the number of elements in the series, ...
    (comp.lang.cpp)
  • Re: tell me if this is right.
    ... > Now to reduce i've applied the Euclidean algorithm ... Before explicitly finding the GCD, it's worth checking if you can see ... any common factors 'by inspection' ...
    (sci.math)
  • Re: tell me if this is right.
    ... >> Now to reduce i've applied the Euclidean algorithm ... > Before explicitly finding the GCD, it's worth checking if you can see ...
    (sci.math)