11
$\begingroup$

The empty sum and empty product have clear, widely accepted definitions. But I can't seem to find any such definition of an "empty GCD".

The GCD, I'm told, is associative. Hence, given a binary GCD function $\gcd(a, b)$, we can define the n-ary GCD function as $\gcd(a, b, c) \equiv \gcd(\gcd(a, b), c)$.

Extending this "below" the binary case, I'm pretty sure no-one would disagree that the unary case, $\gcd(a) = a$, makes sense. Then, can we say that $\gcd(a) = \gcd(a, \gcd())$?

If so, then we need a value $x = \gcd()$ such that $\forall a$, $\gcd(a, x) = a$. It seems to be an accepted convention that $\gcd(a, 0) \equiv a$, and I don't think there's any other candidate.

So, does it make sense to define $\gcd() \equiv 0$?

Motivation: I was implementing an n-ary gcd() function and got curious about whether I should require at least one argument.

$\endgroup$
2
  • $\begingroup$ Yes, $0$ is the only good candidate for empty gcd, just like $1$ is the only good candidate for empty lcm. $\endgroup$
    – Batominovski
    Commented Apr 23, 2016 at 10:50
  • $\begingroup$ Indeed the maximum of $\mathbb Z$ for the (quasi-)order relation "divides" is $0$ hence the GCD of the empty set should be $0$. $\endgroup$
    – Did
    Commented Apr 23, 2016 at 10:50

2 Answers 2

Reset to default
6
$\begingroup$

Yes, the convention $\gcd \emptyset =0 $ makes sense.

Every integer divides all elements of $\emptyset$ thus the "greatest" among them is $0$, when "greatest" is understood with respect to the partial order given by divisibility, which is the appropriate notion of 'size' in this context.

$\endgroup$
5
$\begingroup$

Define $\gcd(S)$ to be natural number $g$ (if it exists) such that:

  1. $g \mid x$ for every $x \in S$.

  2. For any $d$ such that $d \mid x$ for every $x \in S$, we have $d \mid g$.

Then indeed $\gcd(\{\}) = 0$, and moreover it can be proven that $\gcd(S)$ exists for every set $S \subset \mathbb{Z}$.

Also $\gcd(\{0,0\}) = 0$. (This differs from the other common definition of $\gcd$ as the greatest common divisor in terms of size, which would simply stipulate that $\gcd(0,0)$ is undefined.)

$\endgroup$
4
  • 1
    $\begingroup$ Correct! Under this definition, the gcd is the greatest lower bound under the divisibility order relation. The greatest lower bound of the empty set is the maximum in the set (provided it exists) and $0$ is indeed the maximum; the minimum is $1$, as it it a divisor of every element, so the lowest common multiple of the empty set is $1$. $\endgroup$
    – egreg
    Commented Apr 23, 2016 at 10:55
  • $\begingroup$ @egreg: Yep. The question reminds me of math.stackexchange.com/a/544174. $\endgroup$
    – user21820
    Commented Apr 23, 2016 at 10:56
  • $\begingroup$ I've always felt “unnatural” using $\le$ for defining the greatest common divisor, when with the definition you mention it just becomes the greatest lower bound in a lattice, so fitting in a more general framework. $\endgroup$
    – egreg
    Commented Apr 23, 2016 at 11:00
  • $\begingroup$ @egreg: Ah yes that's what you mean. Actually I was simply aiming for a direct clean generalization of the ring-theoretic $\gcd$, specialized to $\mathbb{N}$ for the purpose of this question. It just so happens that it fits nicely into the framework of posets. =) $\endgroup$
    – user21820
    Commented Apr 23, 2016 at 11:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .