Common Divisor Divides GCD

From ProofWiki
Jump to navigation Jump to search


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 \divides a, c \divides b$.


$c \divides \gcd \set {a, b}$

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


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

Then $d \divides a$ and $d \divides 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 \divides a \land c \divides b \implies c \divides u a + v b$ for all $u, v \in \Z$.

Thus $c \divides d$.