Existence of Greatest Common Divisor/Proof 3
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
- 1969: C.R.J. Clapham: Introduction to Abstract Algebra ... (previous) ... (next): Chapter $6$: Polynomials and Euclidean Rings: $\S 28$. Highest Common Factor: Example $54$