Common Divisor Divides GCD

From ProofWiki

Jump to: navigation, search

Theorem

Let $a, b \in \Z$ such that not both of $a$ and $b$ are zero.

Let $c$ be any common divisor of $a$ and $b$.

That is, let $c \in \Z: c \backslash a, c \backslash b$.

Then:

$c \backslash \gcd \left\{{a, b}\right\}$

where $\gcd \left\{{a, b}\right\}$ is the greatest common divisor of $a$ and $b$.

Let $d = \gcd \left\{{a, b}\right\}$.

Then $d \backslash a$ and $d \backslash b$ by definition.

Then from Bézout's Identity, $\exists u, v \in \Z: d = u a + v b$.

From Common Divisor Divides Integer Combination, $c \backslash a \land c \backslash b \implies c \backslash u a + v b$ for all $u, v \in \Z$.

Thus $c \backslash d$.

$\blacksquare$