What is $\gcd(0,0)$?

Question

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common divisor of $0$ and $0$ than $0$.

Answer 1

The word "greatest" in "Greatest Common Divisor" does not refer to being largest in the usual ordering of the natural numbers, but to being largest in the partial order of divisibility on the natural numbers, where we consider $a$ to be larger than $b$ only when $b$ divides evenly into $a$. Most of the time, these two orderings agree whenever the second is defined. However, while, under the usual order, $0$ is the smallest natural number, under the divisibility order, $0$ is the greatest natural number, because every number divides $0$.

Therefore, since every natural number is a common divisor of $0$ and $0$, and $0$ is the greatest (in divisibility) of the natural numbers, $\gcd(0,0)=0$.

Answer 2

I answered this already in a comment at MO: "The best way to think about this is that the "gcd" of two natural numbers is the meet of them in the lattice of natural numbers ordered by divisibility. Note that $0$ is the top element in the divisibility order. The meet of the top element with itself is itself. So $0 = \gcd(0, 0)$ is the answer. 'Greatest' is an unfortunate misnomer in this case."

The book Mathematics Made Difficult has a nice little section on this. It should perhaps better be called "highest common factor" (hcf).

Answer 3

Another way to think about this is ideals. The gcd of two natural numbers $a, b$ is the unique non-negative natural number that generates the ideal $\langle a, b \rangle$. So in this case, $\langle 0 ,0 \rangle$ is just the $0$ ideal so the gcd is $0$.

Answer 4

Simply said - this depends on your definition.

Clearly, if $d=\gcd(a,b)$, you require $d\mid a$, $d\mid b$, i.e., it is a common divisor.

But there are two possibilities how to express that it is greatest common divisor.

One of them is to require $$c\mid a \land c \mid b \Rightarrow c\le d$$ and the other one is $$c\mid a \land c \mid b \Rightarrow c\mid d.$$

Clearly, if you use the first definition, $\gcd(0,0)$ would be the largest integer, so it does not exists. If you use the second one, you get $\gcd(0,0)=0$. (Notice that $0$ is the largest element of the partially ordered set $(\mathbb N,\mid)$.)

As far as I can say, the first definition appears in some text which are "for beginners"; for example here. (It was one of the first results from Google Books when searching for "gcd(0,0)".)

I would say that for students not knowing that $\mid$ is in fact a partial order, the first definition might feel more natural. But once you want to use this in connection with more advanced stuff (for example, g.c.d. as generator of an ideal generated by $a$ and $b$), then the second definition is better.

Answer 5

If we take Euclid's algorithm:

$\text{gcd}(a, b) = \left\{ \begin{array}{l l} a & \quad \text{if $b = 0$}\\ \text{gcd($b$, $a$ mod $b$)} & \quad \text{otherwise} \end{array} \right.$

as the definition of GCD, then $\text{gcd}(a, 0) = 0$ for any $a$, because the stopping case of $b = 0$ is reached immediately. If $a = 0$, then we get $\text{gcd}(0, 0) = 0$.

So, it's possible that Wolfram Alpha obtains its result as a side effect of using Euclid's algorithm rather than deliberate thought as to what gcd(0, 0) should return. But it does fortunately coincide with William's “partial order of divisibility” explanation.

Answer 6

Defining $\gcd(a,b)$ for $\def\Z{\mathbf Z}a,b\in\Z$, to be the non-negative generator of the ideal $a\Z+b\Z$ gives $\gcd(a,0)=|a|$ for all $a$, including for $a=0$. Similarly one can define $\def\lcm{\operatorname{lcm}}\lcm(a,b)$ to be the non-negative generator of the ideal $a\Z\cap b\Z$, which gives $\lcm(a,0)=0$ for all$~a$ (note that since this is the only common multiple in this case, it is unlikely to provoke much discussion).

Adding these cases to the usual definitions of the $\gcd$ and $\lcm$ for nonzero integers causes no problems; all usual formulas remain valid. In fact, if one wants the rule $\gcd(xy,xz)=|x|\gcd(y,z)$ to hold for all integers $x,y,z$, one is forced to put $\gcd(0,0)=0$.

On the other hand, I don't think it is absolutely vital for mathematics to have $\gcd(0,0)$ defined, in the same way as $0+0$, $0\times0$ and $0^0$ need to be defined (and $0/0$ needs to be undefined) in order for the usual rules of algebra that one uses all the time to be valid. I think it would suffice to qualify the rule I cited by "$x\neq0$" if one wants to leave $\gcd(0,0)$ undefined; other rules like $\gcd(a,b)=\gcd(a,a-b)$ do not seem to equate $\gcd(0,0)$ with something else. The reason that leaving it undefined is not so dramatic is that when considering divisibility, $0$ is often excluded anyway; for instance it has to be put aside in the theorem of Unique Factorisation.

Answer 7

In the general framework of integral domains (commutative rings with unity, without nontrivial zero-divisors), we define a greatest common divisor of two elements $a,b$ of an integral domain $R$ as any element $c\in R$ satisfying:

• $c$ divides both $a$ and $b$, that is, there are $x,y\in R$ such that $a=cx$ and $b=cy$.
• If $d\in R$ divides both $a$ and $b$, then $d$ divides $c$.

We write $c=\gcd(a,b)$ in this case. The definition implies that if $c,c^\prime=\gcd(a,b)$, then $c$ and $c^\prime$ are associates, that is $c=uc^\prime$ for some invertible element $u$ in $R$. This is equivalent to say that the principal ideals generated by $c$ and $c^\prime$ are the same. Therefore a non-ambiguous definition is as follows:

"$\gcd(a,b)$ is $\ $ any minimal$\ $ the minimum element in the family $\mathcal F=\{Rd: Rd\supseteq Ra+Rb\}$ of principal ideals containing $a$ and $b$, ordered by inclusion, wherever such minimum ideal exists."

Since $R0+R0=R0$, we see that $R0=0$, the trivial ideal of $R$, is the $\gcd$ of $0$ and $0$.

In general you cannot guarantee that $\gcd$s exist. A sufficient condition is your integral domain $R$ to be a UFD (Unique Factorization Domain).

Answer 8

From Wikipedia:

The greatest common divisor of $a$ and $b$ is well-defined, except for the case $a=b=0$, when every natural number divides them.