33
$\begingroup$

I'm sorry to ask this question but it is important for me to know more about number theory.

I'm confused how $0$ is not divided by itself and in Wolfram Alpha $\gcd(0, 0) = 0$ .

My question here is: is $\gcd(0, 0) = 0$ a wrong belief in mathematics or it is true by convention?

Thank you for any help.

$\endgroup$
  • 7
    $\begingroup$ If one decides to define $\gcd(0,0)$, then $0$ is a good choice. One can choose not to define it. $\endgroup$ – André Nicolas Aug 6 '15 at 14:13
  • 1
    $\begingroup$ Wouldn't the greatest common divisor be infinite since all numbers go into $0$? $\endgroup$ – John Douma Aug 6 '15 at 18:38
  • 6
    $\begingroup$ You can't divide by $0$, but $0$ is a divisor of $0$, because $0\cdot 0=0$. The relation $a\mid b$ means “there exists $c$ such that $b=ac$”. $\endgroup$ – egreg Aug 7 '15 at 15:03
  • 12
    $\begingroup$ This is one of those situations where archaic terminology obscures what ought to be the right definition. "Greatest" makes people think in terms of the usual "$\leq$" ordering of the natural numbers, rather than the partial ordering by divisibility. "Divisor" makes them think about dividing, with its attendant unpleasantness when $0$ is involved. Once you get past the biased terminology, things clear up considerably, as explained in the answers from egreg and Steven Gregory. $\endgroup$ – Andreas Blass Aug 7 '15 at 18:16
  • 1
    $\begingroup$ @Anthony Nobody is saying $0$ is a divisor of anything but $0$. Rather, everything else is also a divisor of $0$. Andreas is postulating that some may oversimplistically think "division and $0$ in the same context, must be impossible" as an explanation for how some may react to the fact $\gcd(0,0)=0$. $\endgroup$ – anon Aug 7 '15 at 19:27

11 Answers 11

40
$\begingroup$

It's not a belief. It's not a convention. It can be proved...

Negative numbers would just be an unnecessary distraction. So we will assume that we are talking about numbers in $\mathbb Z^+ =\{0, 1, 2, 3, \dots\}$

There are two conditions that $g$ must meet to be called the greatest common divisor $(\gcd)$ of $x$ and $y$.

\begin{array}{lll} 1. &g|x \text{ and }g|y &\text{(g is a common divisor of x and y)}\\ 2. &\text{If }z|x \text{ and } z|y \text{, then } z|g &\text{(g is the greatest common divisor of x and y)} \end{array}

As an example, consider the numbers $180$ and $216$. The common divisors of these two numbers are $D_{180,216} = \{1,\,2,\,3,\,4,\,6,\,9,\,12,\,18,\,36\}$ The elements of $D_{180,216}$ are all of the numbers that satisfy condition $(1).$

Here is where things get different than you might think they are. Your immediate reaction might be to say that $36$ is the greatest common divisor because all of the other numbers in $D_{180,216}$ are less than $36$. No, that's wrong. Look more closely at condition $(2)$. The reason that $36$ is the greatest common divisor is that all of the other numbers in $D_{180,216}$ are divisors of $36$. This is a much more subtle and sophisticated thing:

Every list of the common divisors of two numbers contains exactly one number that all of the other numbers in that list divide into. That number is the greatest common divisor.

So how do we prove that $\gcd(0,0) = 0$?

It turns out that there are two definitions of $a|b$.

DEFINITION A. Let $a,b \in \mathbb Z^+.$ Then $a|b$ if and only if there exists an $n \in \mathbb Z^+$ such that $b = an$.

DEFINITION B. Let $a,b \in \mathbb Z^+.$ Then $a|b$ if and only if there exists an $n \in \mathbb Z^+$ such that $\dfrac ba = n$.

The two definitions are exactly the same except, by definition A, $0|0$ is true, and by definition B, $0|0$ is at best undefined. Defining $0|0$ to be true makes the two definitions equivalent to each other.

I found that Wolfram's mathworld uses definition B. Wikipedia lists both definitions. Every algebra and number theory book I own uses definition A.

Personally, I am appalled to see definition B because definition A is necessary to generalize the concept of "divides" to principle ideal domains. One other misconception should be addressed here. There seems to be a belief that $a|b$ implies that $a \le b$. That isn't always true. According to either definition, $4|0$ (Since $\dfrac 04 = 0$ and $0 = 4 \cdot 0$) but $4 \nleq 0$.

Since $0 = x \cdot 0$ for all $x \in \mathbb Z^+$, the divisors of $0$ are $D =\{0,1,2,3,4,\dots\}$ So the common divisors of $0$ and $0$ are $D_{0,0}=D =\{0,1,2,3,4,\dots\}$. The one number in that list that all of the other numbers divide into is $0$.

Hence $0 = \gcd(0,0)$.

I suppose the answer to your question is that it depends. If you accept definition(A), then $\gcd(0,0) = 0$ can be proved. If you accept definition(B), then you have to define $\gcd(0,0) = 0$ so that it agrees with the consequences of definition(A).

$\endgroup$
  • 1
    $\begingroup$ According to mathworld.wolfram.com/Divides.html, $n|0$ for all integers $n$ "by convention", except when $n=0$. Doesn't this mean anything other than $g=0$ satisfies those conditions? $\endgroup$ – Sultan of Swing Aug 7 '15 at 15:06
  • 3
    $\begingroup$ @SultanofSwing In a commutative ring $R$, we have $a\mid b$ by definition if and only if there is a $c\in R$ with $b = ac$. So $n\mid 0$ by definition. Well, one definition. One can make other definitions (but that one is IMO the most natural and convenient), and then it may be a matter of convention. $\endgroup$ – Daniel Fischer Aug 7 '15 at 15:21
  • 1
    $\begingroup$ I think @SultanofSwing meant that the convention that "zero does not divide zero" doesn't really make sense in their last comment. $\endgroup$ – Daniel Fischer Aug 7 '15 at 15:37
  • 1
    $\begingroup$ @StevenGregory I suppose I failed to pay closer attention to condition (2). Doh. Anyways, I just thought I'd point out this "convention" according to "Hardy and Wright 1979, p. 1", that's all. $\endgroup$ – Sultan of Swing Aug 7 '15 at 15:40
  • 1
    $\begingroup$ @GregMartin. If you are only looking at positive integers, then you are right since both definitions coincide. But I you want the entire ring of ingegers or anything more abstract, then you are just wrong. see this $\endgroup$ – steven gregory Aug 12 '15 at 5:27
18
$\begingroup$

Well it depends.

When we define the GCD for two integers, the definition makes sense as long as at least one of the integers is not zero. And whenever when you deal with divisibility problems, $\gcd(0, 0)$ doesn't make sense.

Now, if you know a bit of algebra, there is another way of characterizing (i.e. identifying) the GCD of two integers:

The ideal generated in $\mathbb Z$ by $a$ and $b$ is a Principal Ideal. This ideal is generated by $\gcd(a, b)$ or by $-\gcd(a,b)$. Now, this definition is equivalent to the original one for $(a, b) \neq (0, 0)$ and can be extended naturally to the case $a = 0, b = 0$. With this definition we get $\gcd(0, 0) = 0$.

When using results/tools from Ring theory, one might want to use this convention. This way, one can get slightly more general results, and there is no need to worry at every step if we are in the case $(0, 0)$.

$\endgroup$
  • $\begingroup$ +1 for the ring theory point of view. It looks a lot cleaner than all that divisibility stuff. $\endgroup$ – lisyarus Aug 7 '15 at 15:08
  • 2
    $\begingroup$ @lisyarus One can define gcds for commutative rings (they don't always exist), but once again the "greatest" part does not mean greatest in the sense of an additive linear ordering - very rarely is there any such ordering! Rather, greatest is again with respect to the divisibility ordering. $\endgroup$ – anon Aug 7 '15 at 19:46
  • 1
    $\begingroup$ The beauty of defining $\gcd$, using the ring and ideal structure of $\mathbb{Z}$, is that it can be generalized to commutative rings as anon has pointed out, and that you can define $\text{lcm}$ in a similar fashion. Hence, $\text{lcm}(m,0)=0$ for all $m\in\mathbb{Z}$. $\endgroup$ – Batominovski Aug 12 '15 at 1:52
12
$\begingroup$

This is one of those question that raise religious wars. ;-)

The greatest common divisor was considered first when $0$ was not listed among numbers and it was defined as the largest (under the usual ordering) common divisor. But things change over the centuries.

In what follows, number will mean “natural number” (zero included).

Some people say that every nonzero number $n$ divides $0$, because $n\cdot 0=0$, but they don't accept $0\mid 0$. On the other hand, the definition for $a\mid b$ expressed as “there exists a number $c$ such that $ac=b$” clearly includes $0\mid 0$. One could add “unique”, so in this case $0$ would not divide $0$. As you see, it's just a matter of definitions.

Let's consider the usual ordering of numbers:

$a\le b$ if and only if there exists $c$ such that $a+c=b$

If we compare to the above definition of divisibility

$a\mid b$ if and only if there exists $c$ such that $ac=b$

we surely see an interesting similarity. More interesting is that this defines another order relation on numbers: divisibility is reflexive, antisymmetric and transitive. It's not a total order, because $2\nmid 3$ and $3\nmid 2$, but it's a very interesting ordering nonetheless. Indeed, the ordered set of numbers under divisibility is a lattice: any two elements have a greatest lower bound and a least upper bound.

The greatest lower bound of $a$ and $b$ is a number $d$ such that

  1. $d\mid a$ and $d\mid b$ ($d$ is a lower bound)
  2. for all $c$, if $c\mid a$ and $c\mid b$, then $c\mid d$ ($d$ is the greatest lower bound)

Of course, the greatest lower bound of a single element is the element itself.

What's this greatest lower bound? Of course it is the greatest common divisor in all cases when one among $a$ and $b$ is nonzero. And there's no point in excluding the element $0$ which, in this ordering is the maximum element, because $n\mid 0$ for all $a$ (and $1$ is the minimum).

Once we note that this relation on the natural numbers reflects the partial ordering of ideals in the ring $\mathbb{Z}$ of integers with respect to reverse inclusion, this ordering becomes even more interesting, because the greatest lower bound of two ideals is their sum (and the least upper bound is their intersection), which immediately provides the Bézout relation for the greatest common divisor.

Let's get bold. There are (commutative) rings where the notion of “largest” cannot be given a sensible meaning (think to the Gauss integers), but the notion of greatest common divisor makes sense and is very important. We lose uniqueness, but for any two elements $a$ and $b$ we can find one element $d$ satisfying properties 1 and 2 above.

So, in view of this generalization, the “modern” definition of gcd is more useful and, $\gcd(0,0)=0$ makes no problem. From a computational point of view, restraining ourselves to the natural numbers, perhaps the older definition is better and asking about $\gcd(0,0)$ is rather pointless.

Decide what your definition is and act on consequence. That's all. Allowing $\gcd(0,0)$ requires making exceptions to the rule that $a/\gcd(a,b)$ is a divisor of $a$; on the other hand, not defining it requires making different exceptions. I don't think there are better or worse exceptions: it's a matter of conventions. In some areas a convention may be more useful than another. And, at the end, $\gcd(0,0)$ is not a big deal.

$\endgroup$
  • $\begingroup$ At the risk of starting another disagreement, I've suggested editing this answer to capitalize "GCD" when not within typeset math. $\endgroup$ – user156970 Aug 7 '15 at 19:37
  • 2
    $\begingroup$ I only find one instance of gcd in this answer that is outside of typeset math, and even if there were numerous instances I don't understand why that'd be useful. $\endgroup$ – anon Aug 7 '15 at 19:49
  • $\begingroup$ @egreg, The problem how to convince others as students that gcd(0,0) is 0 or it is wrong belief in math,and in your answer you didn't show if it is true or it is wrong $\endgroup$ – zeraoulia rafik Aug 8 '15 at 0:17
  • 4
    $\begingroup$ @zeraouliarafik It's neither true nor false: it depends on conventions. My personal opinion is that there's no danger in deciding that $\gcd(0,0)=0$, because I'm convinced that the “right” definition is by means of the divisibility order relation. $\endgroup$ – egreg Aug 8 '15 at 5:17
  • $\begingroup$ @egreg. The first time I saw the algebraic definition of gcd was in Moise's calculus book around 1969. Once I worked out what the definition was saying, I was amazed at the sheer chutzpah of that definition. I checked out wikipedia, and they didn't even formally define gcd. I wonder what it woud take to edit the damn thing? $\endgroup$ – steven gregory Aug 12 '15 at 5:58
6
$\begingroup$

You're right to be reluctant to accept the validity of $\gcd(0, 0) = 0$. A lot of times, questions about 0 lead to graph discontinuities and existential quandaries.

Given nonzero integers $a$ and $b$, $$\frac{a}{\gcd(a, b)}$$ is a divisor of $a$ and $$\frac{b}{\gcd(a, b)}$$ is a divisor of $b$. Now, think for a moment about $\gcd(a, 0)$ when $a \neq 0$. ProofWiki tells us that $\gcd(a, 0) = |a|$. For example, with $a = -3$ we have $\frac{-3}{3} = -1$, which is certainly a divisor of $-3$, and $\frac{0}{3} = 0$, which we can choose to accept as a divisor of 0 (more on that choice later).

So far we have not triggered the division by zero error. But if we then ask what the divisors of 0 are, then we run into that problem. And then we also have to re-examine the definition of divisor, a definition we take for granted when dealing with positive as well as with negative integers. Given nonzero integers $a$ and $b$, we say $b$ is a divisor of $a$ if $\frac{a}{b}$ is an integer. For example, $-3$ is a divisor of $-27$ since $\frac{-27}{-3} = 9$. But $-6$ is not a divisor of $-27$ because $\frac{-27}{-6} = \frac{9}{2}$, which is not an integer (though it is a rational number).

Furthermore, each positive integer is one of its own divisors, and its list of divisors is a finite sequence. Thus, if $a > 0$, then $\gcd(a, a) = a$. With minor adjustments we can say the same thing for each negative integer. Indeed, if $a \neq 0$, then $\frac{a}{a} = 1$. But as you already know, $\frac{0}{0}$ is undefined or invalid.

So we reach the seemingly absurd conclusion that every positive integer and every negative integer is a divisor of 0, but 0 itself is not its own divisor. Someone commented earlier that this means that $\gcd(0, 0) = \infty$. Or one could say that $\gcd(0, 0) = -\infty$ for the pure heck of it. But neither $\infty$ nor $-\infty$ are specific integers.

No matter how large two positive integers might be, they each still have a finite list of divisors. The intersection of two finite sets is also finite, and can therefore (at least theoretically, in the case of large integers beyond our practical computational ability) be sorted to find a divisor in common that is greater than all the other common divisors.

But 0 has an infinite list of divisors. Even if we accepted 0 as being its own divisor (which we don't), it's still smaller than, say, $5^{4^{3^2}}$. And then there's $5^{4^{3^2}} + 1$, $5^{4^{3^2}} + 2$, etc., ad infinitum. Therefore $\gcd(0, 0)$ is undefined.

This is all fine and dandy, but if you're programming a calculator or a computer algebra system, do you really want to throw an error message for every little undefined thing that comes your way? You also have to consider that programmers like to build functions on top of other functions. If you have to program GCD, do you implement the Euclidean algorithm (which might not always be the most efficient, e.g., two consecutive Fibonacci numbers) or do you build it on top of FactorInteger?

Try computing $\gcd(8, 13)$. The quickest way is to factorize $8 = 2^3$ and note that 13 is prime. Thus $\gcd(8, 13) = 1$. Now try this in Wolfram Alpha: FactorInteger[0]. Is it any wonder that Wolfram Alpha gives you 0 for GCD[0, 0]? Also try

  • Table[GCD[n, n], {n, -10, 10}]
  • Table[GCD[n, n + 2], {n, -10, 10}]

(That second one gives a $-2$ in the middle that sticks out like a sore thumb).

In conclusion, $\gcd(0, 0) = 0$ is wrong, though I don't know if a lot of people believe it. I think that if you choose to treat it as if it were true, it would be for convenience, not convention.

$\endgroup$
  • 1
    $\begingroup$ Well the convention also makes sense in the context of ring theory and such. It's along the same lines of "is $1$ prime or not?" You could choose it to be prime, or not, but some things are much easier stated if you assume it is not prime. For instance, the uniqueness part of the fundamental theorem of arithmetic holds. It would not if $1$ was not prime. We'd also have to say "assume $p$ is a prime that is not $1$" in damn near every important theorem. $\endgroup$ – Cameron Williams Aug 7 '15 at 15:47
  • 2
    $\begingroup$ @Cameron I think a much closer analogy would be the question "What is $0^0$?" $\endgroup$ – Robert Soupe Aug 7 '15 at 16:28
  • 3
    $\begingroup$ I surely accept $0$ as a divisor of $0$, so your “we don't” is inappropriate. ;-) $\endgroup$ – egreg Aug 7 '15 at 17:23
  • 3
    $\begingroup$ We don't say that b is a divisor of a if a/b is an integer. We say that b is a divisor of a if there exists an integer n such that a = bn. We do this because it avoids having to divide by 0. You said that, if $a, b \ne 0$ then $\dfrac{b}{\gcd(a,b)}$ is an integer. This is true, but it's a theorem not a definition. $\endgroup$ – steven gregory Aug 7 '15 at 17:33
  • 1
    $\begingroup$ @Steven That sounds reasonable enough. Are you also going to tell me that $0 > 1$? $\endgroup$ – Robert Soupe Aug 7 '15 at 17:40
6
+25
$\begingroup$

We will use
$\mathbb N = \{1, 2, 3, 4, \ldots\}$ (the set of natural numbers) and
$\mathbb W = \{0, 1, 2, 3, \ldots\}$ (the set of whole numbers).

First we will define divides and gcd over $\mathbb N$. Then we will look at some of the consequences of those definitions, and finally we will look for a mathematically sound way to extend the definitions of divides and gcd to $\mathbb W.$


DIVIDES and GCD over $\mathbb N$


DEFINITION $1.1.$ For all $x, y \in \mathbb N,$ we say that $x$ divides $y$, writen $x|y$, if $\dfrac yx$ is in $\mathbb N.$

LEMMA $1.2.$ For all $x, y \in \mathbb N,$ $x|y$ if and only if there exists an $n \in \mathbb N$ such that $y = nx.$

COROLLARY $1.2.A.$ For all $x, y \in \mathbb N,$ if $x|y$ then $x \le y.$

So, for example $3|15$ because $\dfrac{15}{3}$ is a natural number and because $15=3 \cdot 5.$

DEFINITION $1.3.$ For any $n \in \mathbb N,$ we define the divisors of $n$ to be the set $D_n=\{x \in \mathbb N: x|n\}$

THEOREM $1.4.$ For each $x,y \in \mathbb N,$ there exists a unique $g \in \mathbb N$ such that $D_x \cap D_y = D_g.$

Proof. Consider the prime decompositions $x=\prod_{i=1}^{\infty}p_i^{\alpha_i}$ and $y=\prod_{i=1}^{\infty}p_i^{\beta_i}$ where there exists some $N \ge 1$ such that $\alpha_i = \beta_i = 0$ for all $i \ge N.$ It isn't hard to verify that $g = \prod_{i=1}^{\infty} p_i^{\gamma_i}$ where $\gamma_i = \min(\alpha_i, \beta_i)$ for all $i\ge 1$.

DEFINITION $1.5.$ For each $x,y \in \mathbb N, \gcd(x,y)$ is the unique $g \in \mathbb N$ such that $D_x \cap D_y = D_g.$

COROLLARY $1.5.A.$ For each $x,y \in \mathbb N, \gcd(x,y) = g$ if and only if \begin{array}{ll} (1.) & g|x \text{ and } g|y\\ (2.) & \text{If } z|x \text{ and } z|y \text{, then } z \le g \end{array}

COROLLARY $1.5.B.$ For each $x,y \in \mathbb N, \gcd(x,y) = g$ if and only if \begin{array}{ll} (1.) & g|x \text{ and } g|y\\ (2.) & \text{If } z|x \text{ and } z|y \text{, then } z|g \end{array}


How much trouble does trying to handle $0$ cause?


DEFINITION $1.1$ Almost still works with $0$ thrown in. We can claim, for example, that $4|0$ since $\dfrac 04 = 0.$ But, since $\dfrac 00$ is undefined, we can't decide if $0|0$ is True or False.

LEMMA $1.2$ Is the key to the problem. If we convert this lemma into a definition, then we haven't changed how "divides" works for the natural numbers and now, we can demonstrate that $0|0.$

COROLLARY $1.2.A$ is now False since $4|0$ yet $4 \nleq 0.$ But, "divides" is a partial order and, with respect to that order, $4|0$ indicates that 0 is greater than 4.

DEFINITION $1.3$ Would be fine, except it might seem odd that $D_0 = \mathbb W.$

THEOREM $1.4$ is still true.

DEFINITION $1.5$ Will still make sense.

COROLLARY $1.5.A$ would no longer be true.

COROLLARY $1.5.B$ would still work if we claimed that $0|0$


DIVIDES and GCD over $\mathbb W$


So, how are we to handle $0?$ What follows is essentially the modern approach. In this approach, $0|0$ and $\gcd(0,0) = 0.$

DEFINITION $1.1.$ For all $x, y \in \mathbb W,$ $x|y$ if and only if there exists an $n \in \mathbb W$ such that $y = nx.$

So $0|0$ because $0 = 0 \cdot 0.$

DEFINITION $1.3.$ For any $n \in \mathbb W,$ we define the divisors of $n$ to be the set $D_n=\{x \in \mathbb W: x|n\}$

In particular, $D_0 = \mathbb W.$

THEOREM $1.4.$ For each $x,y \in \mathbb W,$ there exists a unique $g \in \mathbb W$ such that $D_x \cap D_y = D_g.$

In particular, $D_0 \cap D_0 = D_0.$

Proof. Use the old proof for $x, y \gt 0.$ The special cases are easy to handle.

DEFINITION $1.5.$ For each $x,y \in \mathbb W, \gcd(x,y)$ is the unique $g \in \mathbb N$ such that $D_x \cap D_y = D_g.$

It follows that $\gcd(0,0) = 0.$

COROLLARY $1.5.B.$ For each $x,y \in \mathbb W, \gcd(x,y) = g$ if and only if \begin{array}{ll} (1.) & g|x \text{ and } g|y\\ (2.) & \text{If } z|x \text{ and } z|y \text{, then } z|g \end{array}

Note that one way to read condition (2) is that it indicates that $g$ is the "greatest" divisor or $x$ and $y$ with respect to the partial order $divides$.

$\endgroup$
5
$\begingroup$

This question is strongly related to the question Why doesn't $0$ being a prime ideal in $\mathbb Z$ imply that $0$ is a prime number?. Let me quote a sentence from Pete L. Clark's accepted answer to that question.

Contemporary algebraists often think about factorization as a property of monoids rather than integral domains per se.

I fully agree with this point of view. Thus here we consider $\mathbb{N}$ as a commutative monoid under multiplication. Here is another quote from the same answer.

... Thus we can think of factorization questions as taking place in the cancellative monoid ...

That is, the usual definition considers the cancellative monoid $\mathbb{N} - \{0\}$ still under multiplication. In other words, when dealing with the notions of factorization, prime element, irreducible element, lcm, gcd and so forth on natural numbers, we simply ignore $0$.

Now, this question insists on using $0$, doesn't it? At the level of monoids, a more general question can be asked.

Are there any coherent notions of factorization, prime element, irreducible element, lcm, gcd that work for non-cancellative commutative monoids?

The answer is yes, but it requires to define carefully a few notions. Let $M$ be a commutative monoid with identity $1$. For convenience, I will denote by $\preccurlyeq$ the divisibility relation (that is $a \leqslant b$ if there exists $x \in M$ such that $ax = b$). I will also assume, for simplicity, that $\preccurlyeq$ is a partial order, that is $a \preccurlyeq b$ and $b \preccurlyeq a$ imply $a = b$. This is certainly the case for $\mathbb{N}$.

Then the gcd of a finite family $(x_i)_{i \in I}$ of elements of $M$ can be defined as the infimum (or greatest lower bound) of the set $\{x_i \mid i \in I\}$ with respect with $\leqslant$. Of course, it does not always exist, but in our case, the gcd of $0$ and $0$ exists and is equal to $0$ since $0 \preccurlyeq 0$ and $n \preccurlyeq 0$ for every $n$. This answers the question, but let me go beyond this rather trivial example.

We first need a clean definition of irreducible and prime elements in a commutative monoid:

Definition. An element $x$ is irreductible if, for each finite family $(x_i)_{i \in I}$ such that $x = \prod_{i \in I}x_i$, there exist $i \in I$ such that $x_i = x$.

Definition. An element $x$ is prime if, for each finite family $(x_i)_{i \in I}$ such that $x \preccurlyeq \prod_{i \in I}x_i$, there exist $i \in I$ such that $x_i \preccurlyeq x$.

It is easy to see that every prime element is irreducible, but the converse is not true in general.

Definition. A decomposition of $x$ is a finite family $D = (x_i)_{i \in I}$ of irreducible elements such that $x = \prod_{i \in I}x_i$.

Decompositions of a given element can be compared as follows. Given $D = (x_i)_{i \in I}$ and $D' = (x'_i)_{i \in I'}$ two decompositions of $x$, we say that $D$ is more reduced than $D'$ (notation $D \leqslant D'$) if there exists an injection $\sigma: I \to I'$ such that, for all $i \in I$, $x_i \preccurlyeq x'_i$. One can show that this defines a preorder on the set of all decompositions of a given element. A minimal element of this set is called a reduced decomposition of $x$.

Now comes the main definition.

Definition. A commutative monoid is said to be factorial if each of its elements admits a reduced decomposition.

Note that in a factorial monoid, an element can have several decompositions, but only one reduced decomposition (up to the order of the factors). Here is a simple example.

Let $M = \{1, p, q, r, 0\}$ where $p$, $q$ and $r$ are idempotent $qr = rq = q$ and $pr = rp = pq = qp = 0$. Then $1 \preccurlyeq p \preccurlyeq 0$ and $1 \preccurlyeq r \preccurlyeq q \preccurlyeq 0$, $p$ and $q$ are primes, $r$ is irreducible but not prime. The reduced decompositions of $1$ and $0$ are $1 = \prod_{i \in \emptyset}x_i$ (yes, the empty product is allowed!) and $0 = pr$. $0 = pq$ is another decomposition of $0$, but not a reduced one.

One can show that lcm's always exist in a factorial monoid, but gcd's do not necessarily exist.

$\endgroup$
3
$\begingroup$

One of the very first difficulties in trying to use the Euclidean algorithm to validate $\gcd(0, 0)$ is the problem of division by zero. As a way around this difficulty, I suggest the trial-and-error version of the algorithm.

Instead of trying to compute $a \over b$ to determine $q_1$ for $a = q_1 b + r$, you try setting $q_1 = 1$. If then $r > b$, you increment $q_1$ until $r \leq b$. e.g., $\gcd(24, 10)$, you get $24 = 1 \times 10 + 14$, and since $14 > 10$, you try $24 = 2 \times 10 + 4$.

So for $\gcd(0, 0)$ you get $0 = 1 \times 0 + 0$, concluding that $\gcd(0, 0) = 0$ as desired.


This implementation of the algorithm is of course inefficient for dealing with positive $a$ and $b$. A slight optimization would be this change: "If then $r \geq b$, you increment $q_1$ until $r < b$." But if I had said that from the get-go, it would have created yet another difficulty.

$\endgroup$
2
$\begingroup$

For those who find my previous answer TLDR, here's what it boils down to:

A nonzero integer $a$ has a finite set of divisors, and so does a different nonzero integer $b$. The common divisors of $a$ and $b$ are the intersection of the divisors of $a$ and the divisors of $b$, and this intersection is also finite, which means there is a number among the common divisors that is greater than all the other common divisors: that's the greatest common divisor. If $a = b$, then we only need to look at one set of divisors, which is still finite.

But every integer is a divisor of 0 (except 0 itself). Whatever positive integer we look at, no matter how large and unreachable it may seem to us, is still smaller than the next higher positive integer. Even if we were to accept 0 as its own divisor, it is still smaller than all the positive integers, and therefore it can't be its own greatest common divisor.

Therefore $\gcd(0, 0) = 0$ is wrong. As for why a given computer program would give you that answer, that depends on how the program was written (I go a little more in detail on that in my longer answer).

$\endgroup$
  • 2
    $\begingroup$ Sure $0$ is a divisor of $0$. There is a $c\in \mathbb{Z}$ with $0 = 0\cdot c$. There are in fact a lot of such $c$. $\endgroup$ – Daniel Fischer Aug 7 '15 at 16:43
  • 5
    $\begingroup$ @RobertSoupe But the "greatest" refers to the divisibility preorder, in which $0$ is the greatest integer. Yes, that's not how back in the days people thought about it when the term was coined, but it's the much more general and useful concept. $\endgroup$ – Daniel Fischer Aug 7 '15 at 16:49
  • 1
    $\begingroup$ A reflexive and transitive relation. See wikipedia article. A preorder is "almost a partial order", but you can have $x \leqslant y$ and $y\leqslant x$ without having $x = y$. $\endgroup$ – Daniel Fischer Aug 7 '15 at 17:03
  • 2
    $\begingroup$ No, $0 \nmid 3$, so $\gcd(3,0) = 3$ (or, if we look at $\mathbb{Z}$, then $-3$ is also a $\gcd$ of $0$ and $3$). The thing is that if you have general commutative rings in mind, then the divisibility preorder and $\gcd(0,0) = 0$ are the natural way to look at it. If you focus on $\mathbb{N}$ or maybe $\mathbb{Z}$, then the exception for $\gcd(0,0)$ and the natural ordering of integers can be preferable. See also egreg's new answer. $\endgroup$ – Daniel Fischer Aug 7 '15 at 18:41
  • 2
    $\begingroup$ @zeraouliarafik Unimportant. In a ring with zero divisors (fun terminology fact: every ring element divides $0$, but not every ring element is a zero divisor), you can't expect uniqueness anyway. $\endgroup$ – Daniel Fischer Aug 8 '15 at 8:19
2
$\begingroup$

What is gcd? It is the greatest common divisor. Divisor is something that divides, wholly here. It is defined for natural numbers and $0$ isn't a natural number. Even if you extend it to integers, $0$ cannot divide a number without resulting in undefined. And moreover $0$ over any number is $0$. Thus IMO, $\gcd(0,0)=\infty$.

$\endgroup$
  • $\begingroup$ Explain the downvote. $\endgroup$ – Aditya Agarwal Aug 14 '15 at 15:21
  • 1
    $\begingroup$ Because you ignored a concept that was recently invented for the whole purpose of making me look foolish. $\endgroup$ – Robert Soupe Aug 14 '15 at 16:20
  • 1
    $\begingroup$ Because you men like to be mean to each other. When you can't punch each other in the face, you resort to redefining basic mathematical concepts in terms of exotic objects and then raining down scorn on those who are unaware of this redefinition. $\endgroup$ – Lisa Aug 14 '15 at 18:16
  • 1
    $\begingroup$ Didn't see your answer, sorry. @RobertSoupe $\endgroup$ – Aditya Agarwal Aug 15 '15 at 4:15
  • $\begingroup$ No problem, the scrollbar is getting very small on this one. @AdityaAgarwal $\endgroup$ – Robert Soupe Aug 15 '15 at 15:47
1
$\begingroup$

A lightning rod answer: since the Euclidean algorithm is regarded so highly, and not just for boring old $\mathbb{Z}$, if $\gcd(0, 0)$ is valid, then it must be computable using the Euclidean algorithm.

Going by http://mathworld.wolfram.com/EuclideanAlgorithm.html to start off the computation of $\gcd(a, b)$ we set $$q_1 = \big\lfloor \frac{a}{b} \big\rfloor.$$ But $\big\lfloor \frac{0}{0} \big\rfloor$ is undefined, and therefore $\gcd(0, 0)$ must also be undefined.

$\endgroup$
  • 1
    $\begingroup$ The Euclidean algorithm only requires subtraction. Given $(0,0)$ it would output $0$. $\endgroup$ – ASCII Advocate Aug 14 '15 at 19:23
  • $\begingroup$ @ASCII After reviewing the Mathworld page Lisa linked, it seems to me like they could be a little clearer on that point. As it stands, it seems perfectly reasonable for someone reading it to conclude that some divisions are required to obtain this thing that's called a divisor. $\endgroup$ – Robert Soupe Aug 15 '15 at 2:52
  • 1
    $\begingroup$ I guess "classical" or "Euclid's" Euclidean algorithm would describe more clearly which version I was talking about, that replaces $(a,b)$ with $(a-b,b)$ or $(b,a)$ at every step. That is the one more typical of number theory textbooks and theoretical math conversations, and less typical of actually utilized algorithms run by hand or on a computer. I think the procedure taught in school as part of basic arithmetic, is more often the one that does use integer division. @RobertSoupe $\endgroup$ – ASCII Advocate Aug 15 '15 at 3:14
  • 2
    $\begingroup$ This answer misunderstands what $a|b$ means $\endgroup$ – Squirtle Aug 17 '15 at 19:06
1
$\begingroup$

Let $D$ be a principal ideal domain; that is, given any ideal $I$ there exists some element, say $a\in I$, such that $I=(a)=\{b.a|b\in D\}$. It follows, by definition, that $\mathbb{D}=(D\backslash \{0\}, \cdot, 1)$ is a commutative cancellation monoid. We define the divisibility relation $a|b$ if and only if $ac=b$ for some $c\in D$. Then $$1|a \text{ and } a|0$$ for any $a\in D$. Define $(D/\sim, |)$ with $a\sim b$ if and only if $a|b$ and $b|a$. Observe $$a|b \text{ if and only if } (a)\supset (b)$$

That is, $[0]$ is the maximum of the ordered set $(D/\sim, |)$ (because $0$ is in every ideal).

Now just apply the definition of "greatest common divisor".

$\endgroup$
  • $\begingroup$ I'm upvoting, but I'm also wondering if it is at all possible to come to this conclusion without ideals, monoids, etc. If Euclid knew English, would this make any sense to him? $\endgroup$ – user156970 Aug 17 '15 at 21:07
  • 1
    $\begingroup$ It would be very easy to explain what an ideal, etc... is to Euclid. Also, I think that modern language exists because it works. $\endgroup$ – Squirtle Aug 17 '15 at 22:59

protected by Jyrki Lahtonen Aug 14 '15 at 15:31

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.