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

• It is typically not defined. Commented Sep 16, 2013 at 4:58
• – anon
Commented Sep 16, 2013 at 5:23
• A fancy expression: $\gcd(a, b) = \operatorname{char} \mathbb{Z}/(a, b)$.
– Orat
Commented Dec 20, 2018 at 19:02
• $\gcd(0,0) = 0\$ by $\, d\mid 0,0\iff d\mid 0,\,$ see the GCD Universal Property $\ \$ Commented Nov 6, 2019 at 21:12

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
Commented Sep 16, 2013 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? Commented Sep 16, 2013 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). Commented Sep 16, 2013 at 11:55
• Euclid, I mean.... Commented Sep 16, 2013 at 14:50
• @KonstantinWeitz I wish such an Official Book of All Mathematical Definitions existed. It would end every dispute, because one could simply refer to that book and consult the definition and case closed. But guess what: I asked many mathematicians and none could point out any such book :P I'm starting to believe that they're all making things up :P They seem to be able to pull any definition they please up their butt and claim that "because Mathematics says so, so shut up and calculate" ;q Once I was looking for a definition of an angle, and I found over 9 of them, all of them different :P Commented Mar 20, 2017 at 6:26

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. Commented Sep 16, 2013 at 5:05
• we all lost to him :) Commented Sep 16, 2013 at 5:06
• @dfeuer Well, I had answered the question already at MO. I wasn't racing. Commented Sep 16, 2013 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. Commented Sep 16, 2013 at 11:00

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.

• 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. Commented Apr 8, 2015 at 0:46
• What's an ideal, in simple terms? Commented Mar 20, 2017 at 8:30
• @BarbaraKwarc You can have a look at Wikipedia article. Or perhaps this question: Intuition behind “ideal”. Commented Mar 20, 2017 at 9:01

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

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.

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.

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 '. Commented Sep 16, 2013 at 5:11
• I've tried editing it myself, but you've interrupted me twice, so I'll let you do it. Commented Sep 16, 2013 at 5:11
• @dfeuer Thanks for the suggestion. By the way, that ' shortcut works in ordinary $\LaTeX$? Commented Sep 16, 2013 at 5:12
• Yep! It even works in Plain $\TeX$! $x'''$ just takes four keystrokes (six if you count dollar signs). Commented Sep 16, 2013 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. Commented Sep 16, 2013 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. Commented Sep 16, 2013 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$). Commented Sep 16, 2013 at 5:32
• The guy got his answer, that's the most important :) Commented Sep 16, 2013 at 5:33