# Existence of Greatest Common Divisor

## Theorem

$\forall a, b \in \Z: a \ne 0 \lor b \ne 0$, there exists a largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$.

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

## Proof

### Proof of Existence

We have that:

- $\forall a, b \in \Z: 1 \divides a \land 1 \divides b$

so $1$ is always a common divisor of any two integers.

$\Box$

### 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 from Absolute Value of Integer is not less than Divisors:

- $\forall c \in \Z: \forall a \in \Z_{>0}: c \divides a \implies c \le \size c \le \size a$

The same applies for $c \divides b$.

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

\(\displaystyle a \ne 0 \land b \ne 0\) | \(\implies\) | \(\displaystyle \gcd \set {a, b} \le \min \set {\size a, \size b}\) | |||||||||||

\(\displaystyle a = 0 \lor b = 0\) | \(\implies\) | \(\displaystyle \gcd \set {a, b} = \max \set {\size a, \size b}\) | |||||||||||

\(\displaystyle a = b = 0\) | \(\implies\) | \(\displaystyle \forall x \in \Z: x \divides a \land x \divides b\) |

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 Set of Integers Bounded Above by Integer has Greatest Element there is always a **greatest** common divisor.

$\blacksquare$

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: I. Basic Concepts*... (previous) ... (next): Introduction $\S 6$: The division process in $I$ - 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): Chapter $3$: The Integers: $\S 11$. Highest Common Factor: Theorem $19$ - 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): Chapter $6$: Polynomials and Euclidean Rings: $\S 28$. Highest Common Factor: Example $54$ - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\S 2.2$: Theorem $2.2$