[1.6] Greatest Common Divisor of Many Integers (1.6.22 - 1.6.25)
Definition 1.6.22
A natural number \(d\) is the greatest common divisor of nonzero integers \(a_1,a_2,...,a_n\) if
- \(d\) divides each \(a_i\) and
- whenever \(x \in \mathbf{N}\) divides each \(a_i\), then \(x\) also divides \(d\)
Lemma 1.6.23
Given nonzero integers \(a_1,...,a_n (n \geq 2)\), there is a natural number \(d\) and an \(n\)-by-\(n\) integer matrix \(Q\) such that \(Q\) is invertible, \(Q^{-1}\) also has integer entries, and
$$
\begin{align*}
(d,0,...,0) = (a_1,a_2,...,a_n)Q.
\end{align*}
$$
Proof
TODO
Proposition 1.6.24
The greatest common divisor of non-zero integers \(a_1,...,a_n\) exists, and is an integer linear combination of \(a_1, a_2,...,a_n\).
Proof
TODO
Definition 1.6.25
We say that non-zero integers \(a_1,...,a_n\) are relatively prime if their greatest common divisor is 1.
We say that they are pairwise relatively prime if \(a_i\) and \(a_j\) are relatively prime whenever \(i \neq j\).
Lemma 1.6.26
Let \(a_1,...,a_n\) be pairwise relatively prime integers, and let \(a = a_1,...,a_n\). If an integer \(z\) is divisible by each \(a_i\), then \(z\) is divisible by \(a\).
Proof
TODO