Existence of Greatest Common Divisor/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \Z$ be integers such that $a \ne 0$ or $b \ne 0$.

Then the greatest common divisor of $a$ and $b$ exists.


Proof

From Integers form Integral Domain, we have that $\Z$ is an integral domain.

From Euclidean Domain is GCD Domain, $a$ and $b$ have a greatest common divisor $c$.

This proves existence.


From Ring of Integers is Principal Ideal Domain, we have that $\Z$ is a principal ideal domain.

Suppose $c$ and $c'$ are both greatest common divisors of $a$ and $b$.

From Greatest Common Divisors in Principal Ideal Domain are Associates:

$c \divides c'$

and:

$c' \divides c$

and the proof is complete.

$\blacksquare$


Sources