# What is $\gcd(0,a)$, where $a$ is a positive integer?

I have tried $\gcd(0,8)$ in a lot of online gcd (or hcf) calculators, but some say $\gcd(0,8)=0$, some other gives $\gcd(0,8)=8$ and some others give $\gcd(0,8)=1$. So really which one of these is correct and why there are different conventions?

• I haven't encountered the convention of gcd(0,8) = 1. It depends on how you define the phrase "a divides b" Mar 18 '11 at 2:49
• Mar 18 '11 at 2:53
• @The Chaz: They are really the same things but with different names. see en.wikipedia.org/wiki/Greatest_common_divisor Mar 18 '11 at 4:04
• Should be a, because anything is a divisor of 0. Nov 26 '20 at 7:48

Let's recall the definition of  "$\rm a$ divides $\rm b$"  in a ring $\rm\,Z,\,$ often written as $\rm\ a\mid b\ \ in\ Z.$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \rm\ a\mid b\ \ in\ Z\ \iff\ a\,c = b\ \$ for some $\rm\ c\in Z$

Recall also the definition of $\rm\ gcd(a,b),\,$ namely

$(1)\rm\qquad\quad \rm gcd(a,b)\mid a,b\qquad\qquad\qquad\$ the gcd is a common divisor

$(2)\rm\qquad\quad\! \rm c\mid a,b\ \ \ \Longrightarrow\ \ c\mid gcd(a,b)\quad$ the gcd is a greatest common divisor

$\ \ \ \$ i.e. $\rm\quad\ c\mid a,b\ \iff\ c\mid gcd(a,b)\quad\,$ expressed in $\iff$ form  [put $\rm\ c = gcd(a,b)\$ for $(1)$]

Notice $\rm\quad\, c\mid a,0\ \iff\ c\mid a\,\$ so $\rm\ gcd(a,0)\ =\ a\$ by the prior "iff" form of the gcd definition.

Note that $\rm\ gcd(0,8) \ne 0\,$ since $\rm\ gcd(0,8) = 0\ \Rightarrow\ 0\mid 8\$ contra $\rm\ 0\mid x\ \iff\ x = 0.$

Note that $\rm\ gcd(0,8) \ne 1\,$ else $\rm\ 8\mid 0,8\ \Rightarrow\ 8\mid gcd(0,8) = 1\ \Rightarrow\ 1/8 \in \mathbb Z.$

Therefore it makes no sense to define $\rm\ gcd(0,8)\$to be $\,0\,$ or $\,1\,$ since $\,0\,$ is not a common divisor of $\,0,8\,$ and $\,1\,$ is not the greatest common divisor.

The $\iff$ gcd definition is universal - it may be employed in any domain or cancellative monoid, with the convention that the gcd is defined only up to a unit factor. This $\iff$ definition is very convenient in proofs since it enables efficient simultaneous proof of both implication directions. $\$ For example, below is a proof of this particular form for the fundamental GCD distributive law $\rm\ (ab,ac)\ =\ a\ (b,c)\$ slightly generalized (your problem is simply $\rm\ c=0\$ in the special case $\rm\ (a,\ \ ac)\ =\,\ a\ (1,c)\ =\ a\,$).

Theorem $\rm\quad (a,b)\ =\ (ac,bc)/c\quad$ if $\rm\ (ac,bc)\$ exists.

Proof $\rm\quad d\mid a,b\ \iff\ dc\mid ac,bc\ \iff\ dc\mid (ac,bc)\ \iff\ d|(ac,bc)/c$

See here for further discussion of this property and its relationship with Euclid's Lemma.

Recall also how this universal approach simplifies the proof of the basic GCD * LCM law:

Theorem $\rm\;\; \ (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof $\rm\quad d|\,a,b \;\iff\; a,b\,|\,ab/d \;\iff\; [a,b]\,|\,ab/d \;\iff\; d\,|\,ab/[a,b] \quad\;\;$

For much further discussion see my many posts on GCDs.

Another way to look at it is by the divisibility lattice, where gcd is the greatest lower bound. So 5 is the greatest lower bound of 10 and 15 in the lattice.

The counter-intuitive thing about this lattice is that the 'bottom' (the absolute lowest element) is 1 (1 divides everything), but the highest element, the one above everybody, is 0 (everybody divides 0).

So $\gcd(0, x)$ is the same as ${\rm glb}(0, x)$ and should be $x$, because $x$ is the lower bound of the two: they are not 'apart' and 0 is '$>'$ $x$ (that is the counter-intuitive part).

In fact, the top answer can be generalized slightly: if $$a \mid b$$, then $$\gcd(a,b)=a$$ (and this holds in any algebraic structure where divisibility makes sense, e.g. a commutative, cancellative monoid).

To see why, well, it's clear that $$a$$ is a common divisor of $$a$$ and $$b$$, and if $$\alpha$$ is any common divisor of $$a$$ and $$b$$, then, of course, $$\alpha \mid a$$. Thus, $$a=\gcd(a,b)$$.

• Indeed, even more generally, it is a special case of the distributive law - see my answer. As for commutative monoids, one usually requires them to be cancellative in order to obtain a rich theory. Mar 18 '11 at 18:26

It might be partly a matter of convention. However, I believe that stating that $$\gcd(8,0) = 8$$ is safer. In fact, $$\frac{0}{8} = 0$$, with no remainder. The proof of the division, indeed is that "Dividend = divider $$\times$$ quotient plus remainder". In our case, 0 (dividend) = 8 (divisor) x 0 (quotient). No remainder. Now, why should 8 be the GCD? Because, while the same method of proof can be used for all numbers, proving that $$0$$ has infinite divisors, the greatest common divisor cannot be greater than $$8$$, and for the reason given above, is $$8$$.