Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
    
    
@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

3 Answers 3

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.