Existence of Greatest Common Divisor

Theorem

$\newcommand{\gc} [2] {\gcd \left\{{#1, #2}\right\}}$ $\newcommand{\mx} [2] {\max \left\{{\mid {#1}\mid, \mid{#2}\mid}\right\}}$ $\newcommand{\mn} [2] {\min \left\{{\mid {#1}\mid, \mid{#2}\mid}\right\}}$ $\forall a, b \in \Z: a \ne 0 \lor b \ne 0$, there exists a largest $d \in \Z_{>0}$ such that $d \backslash a$ and $d \backslash b$.

The greatest common divisor of $a$ and $b$ always exists.

Proof

• Proof of its existence:

$\forall a, b \in \Z: 1 \backslash a \land 1 \backslash b$ so $1$ is always a common divisor of any two integers.

• Proof of there being a largest:

As the definition of $\gcd$ shows that it is symmetric, we can assume without loss of generality that $a \ne 0$.

First we note that:

$\forall c \in \Z: \forall a \in \Z^*: c \backslash a \implies c \le \left|{c}\right| \le \left|{a}\right|$

... from Integer Absolute Value Greater than Divisors.

The same applies for $c \backslash b$.

Now we have three different results depending on $a$ and $b$:

	\(\displaystyle \)	\(\displaystyle a \ne 0 \land b \ne 0\)	\(\implies\)	\(\displaystyle \gc a b \le \mn a b\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle a = 0 \lor b = 0\)	\(\implies\)	\(\displaystyle \gc a b = \mx a b\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle a = b = 0\)	\(\implies\)	\(\displaystyle \forall x \in \Z: x \backslash a \land x \backslash b\)	\(\displaystyle \)

So if $a$ and $b$ are both zero, then any $n \in \Z$ divides both, and there is no greatest common divisor. This is why the proviso that $a \ne 0 \lor b \ne 0$.

So we have proved that common divisors exist and are bounded above. Therefore, from Integers Bounded Above has Maximal Element there is always a greatest common divisor.

$\blacksquare$

Sources

• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.11$: Theorem $19$
• George E. Andrews: Number Theory (1971): $\S 2.2$: Theorem $2.2$