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

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$.

-
(o,o)? <- see the face scratching the head? – zerosofthezeta Sep 16 '13 at 4:57
It is typically not defined. – copper.hat Sep 16 '13 at 4:58
– anon Sep 16 '13 at 5:23

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$.

-
Similarly $\gcd(0,n)=n$ for all $n\in\Bbb N$ (including $n=0$). – anon Sep 16 '13 at 5:22
Thanks, great answer! How did you figure this out? Where do mathematicians store such commonly agreed on, but not completely obvious definitions? When did people start defining gcd this way, I assume they didn't when Euclidean algorithm was invented 300BC? – Konstantin Weitz Sep 16 '13 at 6:55
For the most part, the partial order of divisibility coincides with the usual ordering wherever it is defined. So if $\le$ represents the usual ordering and $\vert$ represents the partial order of divisibility, then $x\vert y\Rightarrow x\le y$, except if $y=0$. Moreover, if $x$ is a common divisor of two non-zero natural numbers $a$ and $b$, then $x\le\gcd(a,b)\Rightarrow x\vert\gcd(a,b)$. So in most cases, you can define $\gcd(a,b)$ to be the greatest common divisor of $a$ and $b$, where 'greatest' refers to the usual ordering. That's what Euler did (and left $\gcd(0,0)$ undefined). – Donkey_2009 Sep 16 '13 at 11:55
Euclid, I mean.... – Donkey_2009 Sep 16 '13 at 14:50

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).

-
You lost the race to William. – dfeuer Sep 16 '13 at 5:05
we all lost to him :) – DanielY Sep 16 '13 at 5:06
@dfeuer Well, I had answered the question already at MO. I wasn't racing. – user43208 Sep 16 '13 at 5:06
Win or lose, "the meet of [two numbers] in the lattice of natural numbers ordered by divisibility" is a definition of delightful pithiness. – Jordan Gray Sep 16 '13 at 11:00

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$.

-

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.

-

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$. (Note 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 collection 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.

-
This helped. I still feel a little icky about (ℕ,∣) as a partial order, because 0∣0 feels weird to me, and this whole argument requires that reflexivity. – rampion Apr 8 at 0:46

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).

-
Use \gcd instead of $GCD$. Also, ^\prime can be abbreviated all the way down to '. – dfeuer Sep 16 '13 at 5:11
I've tried editing it myself, but you've interrupted me twice, so I'll let you do it. – dfeuer Sep 16 '13 at 5:11
@dfeuer Thanks for the suggestion. By the way, that ' shortcut works in ordinary $\LaTeX$? – Matemáticos Chibchas Sep 16 '13 at 5:12
Yep! It even works in Plain $\TeX$! $x'''$ just takes four keystrokes (six if you count dollar signs). – dfeuer Sep 16 '13 at 5:16
anon- Not on my keyboard. On my keyboard, backtick is the key to the left of 1, and tilde is obtained by holding shift and pressing the hash key (which is next to Enter). In general, the location of punctuation characters varies in keyboards used in different countries. – Hammerite Sep 16 '13 at 9:21

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.

-
Well, this isn't really the right answer, is it? William got it right. – user43208 Sep 16 '13 at 5:22
All I'm saying is that Wikipedia got it wrong in this case (or at least it's misleading to suggest that $\gcd(0, 0)$ is not well-defined, because as has been clearly explained, it's perfectly well-defined and indeed it's $0$). – user43208 Sep 16 '13 at 5:32
The guy got his answer, that's the most important :) – DanielY Sep 16 '13 at 5:33

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.

-