# 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" –  The Chaz 2.0 Mar 18 '11 at 2:49
–  Vafa Khalighi 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 –  Vafa Khalighi Mar 18 '11 at 4:04

First recall the definition of $\rm\:a\:$ divides $\rm\:b\:$ in a ring $\rm\:Z\:,\:$ often written as $\rm\ a\ |\ b\ \ in\ Z\:.$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \rm\ a\ |\ 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\quad\quad\quad\quad\quad\ \rm gcd(a,b)\ |\ a,b\quad\quad\quad\quad\quad\quad\quad\$ the gcd is a common divisor

$(2)\rm\quad\quad\quad\quad\quad\ \rm c\ |\ a,b\ \Rightarrow\ c\ |\ gcd(a,b)\quad\quad$ the gcd is the greatest common divisor

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

Notice $\rm\quad\: c\ |\ a,0\ \iff\ c\ |\ a\:,\$ so $\rm\ gcd(a,0)\ =\ a\$ by the above $\iff$ form of the gcd definition.

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

Note that $\rm\ gcd(0,8) \ne 1\:,\$ else $\rm\ 8\ |\ 0,8\ \Rightarrow\ 8\ |\ 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\ |\ a,b\ \iff\ dc\ |\ ac,bc\ \iff\ dc\ |\ (ac,bc)\ \iff\ d|(ac,bc)/c$

See my post 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 (sorry, I don't have enough points to post comments, yet): if $a \vert b$, then $gcd(a,b)=a$ (and this holds in any algebraic structure where divisibility makes sense (eg 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 \vert 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. –  Bill Dubuque Mar 18 '11 at 18:26