Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$

Let $a, b \in \mathbb{Z}$. An integer $d$ is a common divisor of $a$ and $b$ when $d \mid a$ and $d \mid b$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$). Write

$D(a,b) \;:=\; \{\, d \in \mathbb{Z} \;:\; d \mid a \ \text{ and } \ d \mid b \,\}$

for the set of common divisors.

Case $(a,b) \ne (0,0)$: the greatest element exists. $D(a,b)$ is nonempty, since $1 \mid a$ and $1 \mid b$ for every $a$ and $b$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$). It is bounded above: at least one of $a$ and $b$ is nonzero, say $a \ne 0$ (if instead $b \ne 0$, argue with $b$ throughout), and every $d \in D(a,b)$ divides $a$, so $d \le |a|$ by If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$; hence the set of divisors of a nonzero integer is bounded above by $|a|$. A nonempty set of integers bounded above has a unique greatest element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element), and we define

$\gcd(a,b) \;:=\; \text{the greatest element of } D(a,b).$

Since $1 \in D(a,b)$ and $\gcd(a,b)$ is greatest, $\gcd(a,b) \ge 1$; in particular $\gcd(a,b) > 0$.

Case $(a,b) = (0,0)$: a convention, fixed here. Every integer divides $0$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$), so $D(0,0) = \mathbb{Z}$, which has no greatest element at all: the clause above defines nothing, and leaving $\gcd(0,0)$ undefined would put a hole in every identity below. We therefore set

$\gcd(0,0) \;:=\; 0 .$

With both cases together, $\gcd(a,b)$ is defined for every pair of integers, and $\gcd(a,b) \ge 0$ always.

Why $0$, and not some other value. The convention is not arbitrary, and the reasons are recorded here rather than deferred:

• It is the greatest common divisor in the divisibility ordering. $0$ is a common divisor of $0$ and $0$, and every common divisor of $0$ and $0$ divides $0$. So $0$ is greatest at $(0,0)$ in the sense "divisible by every common divisor", which is the sense that Every common divisor of $a$ and $b$ divides $\gcd(a,b)$; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$, $d \mid a$, $d \mid b$, and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well shows holds at every pair, $(0,0)$ included, whereas "greatest in the order of $\mathbb{Z}$" fails there.
• It is the only value under which the scaling identity extends to this boundary. Requiring $\gcd(ca,cb) = |c|\gcd(a,b)$ to hold at every triple leaves no freedom here. At $c = 0$ with any $(a,b) \ne (0,0)$ it would read $\gcd(0,0) = |0|\gcd(a,b) = 0$, whose right-hand side does not involve $\gcd(0,0)$ at all; and at $a = b = 0$ with $c = 1 + 1$ it reads $g = g + g$, again giving $g = 0$. The value is therefore chosen here, and $\gcd(ca, cb) = |c|\,\gcd(a,b)$ for all integers $a, b, c$, the identity holding at $c = 0$ and at $(a,b) = (0,0)$ as well then proves the identity for every triple with this convention in force; its own $(0,0)$ case reads the value off this definition rather than establishing it.
• It is consistent with the product formula — $\gcd(a,b)\operatorname{lcm}(a,b) = |ab|$ (Every common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a,b)$, and $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |ab|$) reads $0 \cdot 0 = 0$ at $(0,0)$, using $\operatorname{lcm}(0,0) = 0$ from Common multiple, and the least common multiple $\operatorname{lcm}(a,b)$, taken to be $0$ when $a = 0$ or $b = 0$. This one is a check, not a second forcing argument: with $\operatorname{lcm}(0,0) = 0$ the left side vanishes whatever value $\gcd(0,0)$ is given, so the product formula is silent at $(0,0)$ and only the scaling identity above pins the value down.

• The gap the convention fills is real. The failure is exhibited on the companion page by The common divisors of $(0,0)$ are all of $\mathbb{Z}$ and have no greatest element in the order of $\mathbb{Z}$, so $\gcd(0,0)$ cannot be defined as a maximum and is fixed by convention ↗: the common divisors of $(0,0)$ really are all of $\mathbb{Z}$, and really have no greatest element, so a value has to be supplied rather than computed.

• The definition is by a maximum, and the theory replaces it by a divisibility characterisation. Reading $\gcd$ as "largest common divisor" is what makes the $(0,0)$ case awkward, and it is also not the property later pages use. Every common divisor of $a$ and $b$ divides $\gcd(a,b)$; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$, $d \mid a$, $d \mid b$, and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well proves the replacement: $d = \gcd(a,b)$ exactly when $d \ge 0$, $d$ is a common divisor, and every common divisor divides $d$. That statement is uniform across all pairs.

• Sign. $\gcd(a,b)$ is never negative, by construction. Since $-d$ is a common divisor whenever $d$ is (Divisibility is reflexive and transitive on $\mathbb{Z}$, and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$; also $d \mid a$ implies $d \mid ac$, $-d \mid a$ and $d \mid -a$), the set $D(a,b)$ is symmetric about $0$, and taking the greatest element is exactly the choice of the nonnegative representative from each pair of associates (For integers $a$ and $b$ the following are equivalent: $a \mid b$ and $b \mid a$; $b = ua$ for a unit $u$; $|a| = |b|$. Being associates is an equivalence relation whose class of $a$ is $\{a, -a\}$).

• Two arguments, not a list. $\gcd$ is defined here on pairs only. Nothing on this page needs a greatest common divisor of a longer list, and none is defined.