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)\mathrm{\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\mathrm{\ne }0$ (if instead $b\mathrm{\ne }0$, argue with $b$ throughout), and every $d\in D(a,b)$ divides $a$, so $d\le \mathrm{\mid }a\mathrm{\mid }$ by If $d\mid a$ and $a\mathrm{\ne }0$ then $d\mathrm{\ne }0$ and $\mathrm{\mid }d\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }$; hence the set of divisors of a nonzero integer is bounded above by $\mathrm{\mid }a\mathrm{\mid }$. 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)\mathrm{.}$

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)=\mathrm{\mid }c\mathrm{\mid }\gcd (a,b)$ to hold at every triple leaves no freedom here. At $c=0$ with any $(a,b)\mathrm{\ne }(0,0)$ it would read $\gcd (0,0)=\mathrm{\mid }0\mathrm{\mid }\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)=\mathrm{\mid }c\mathrm{\mid }\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)\mathrm{lcm}(a,b)=\mathrm{\mid }ab\mathrm{\mid }$ (Every common multiple of $a$ and $b$ is a multiple of $\mathrm{lcm}(a,b)$, and $\gcd (a,b)\cdot \mathrm{lcm}(a,b)=\mathrm{\mid }ab\mathrm{\mid }$) reads $0\cdot 0=0$ at $(0,0)$, using $\mathrm{lcm}(0,0)=0$ from Common multiple, and the least common multiple $\mathrm{lcm}(a,b)$, taken to be $0$ when $a=0$ or $b=0$. This one is a check, not a second forcing argument: with $\mathrm{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$; $\mathrm{\mid }a\mathrm{\mid }=\mathrm{\mid }b\mathrm{\mid }$. 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.