Finite Set of Elements in Principal Ideal Domain has GCD

From ProofWiki
Jump to navigation Jump to search


Let $\struct {D, +, \circ}$ be a principal ideal domain.

Let $a_1, a_2, \dotsc, a_n$ be non-zero elements of $D$.

Then $a_1, a_2, \dotsc, a_n$ all have a greatest common divisor.


Let $0_D$ and $1_D$ be the zero and unity respectively of $D$.

Let $J$ be the set of all linear combinations in $D$ of $\set {a_1, a_2, \dotsc, a_n}$.

From Set of Linear Combinations of Finite Set of Elements of Principal Ideal Domain is Principal Ideal:

$J = \ideal x$

for some $x \in D$, where $\ideal x$ denotes the principal ideal generated by $x$.

We have that each $a_i$ can be expressed as a linear combination of $\set {a_1, a_2, \dotsc, a_n}$:

$a_i = 0_D a_1 + 0_D a_2 + \dotsb + 1_D a_i + \dotsb + 0_D a_n$


$\forall i \in \set {0, 1, \dotsc, n}: a_i \in J$

and so by definition of $J$:

$\forall i \in \set {0, 1, \dotsc, n}: a_i = t_i x$

for some $t_i \in D$.

Thus $x$ is a common divisor of $a_1, a_2, \dotsc, a_n$.

As $x \in \ideal x = J$, we have:

$x = c_1 a_1 + c_2 a_2 + \dotsb + c_n a_n$

for some $c_1, c_2, \dotsc, c_n \in D$.

Thus every common divisor of $a_1, a_2, \dotsc, a_n$ also is a divisor of $x$.

Thus $x$ is a greatest common divisor of $a_1, a_2, \dotsc, a_n$.