# Proof, that every nonempty set of integers, not all zero, has a greatest common divisor

I'm searching for a proof or (better) a way to understand the proof from the book "Elementary methods in number theory", that every nonempty set of integers, not all zero, has a greatest common divisor.

The proof in the book starts like this:

Proof: Let $H$ be the subset of $\mathbb{Z}$ consisting of all integers of the form $a_1x_1 + \dots + a_kx_k$ with $a_1, \dots, a_k \in A$ and $x_1,\dots, x_k \in \mathbb{Z}$. Then....

However, I don't see, how the $k$ is chosen, since we are not assuming, that $A$ has to be finite. I suppose, it also matters, which $a_1, \dots, a_k$ we pick.

I tried something slightly different, which is still similar to the proof in the book:

Proof: There are finitely many common divisors of $A$, call them $d_1, \dots, d_n$. Then the set $G$ of linear combinations of $d_1, \dots, d_n$ is a subgroup of $(\mathbb{Z},+)$, so there is a $d\in \mathbb{N}_0$ with $G = d\mathbb{Z}$. Since $A\subseteq G$, there is a $z\in \mathbb{Z}$ for each $a\in A$ with $a=dz$, hence $d|a$.

I don't know how to show, that $d_1, \dots, d_n | d$, though.

I think your proof has some problems. One is that you haven't shown that there are a finite number of common divisors of $A$. It's not too hard to do that:

Let $A$ be any nonempty subset of $\mathbb{Z}$. Then the set

$$B = \{|x| \text{ s.t. } x \in A\}$$

is a nonempty subset of $\mathbb{N} \cup \{0\}$. Since $\mathbb{N}$ is well-ordered, $B$ must have a least element, $b$. Since any common divisor of $A$ must be less than or equal to $b$, a fortiori $b$ is an upper bound on the $\gcd$ of $A$. Since the $\gcd$ is positive, this gives us a finite number of possible common divisors, so we can enumerate them $d_1, \dots d_n$ as you've done.

Once you've shown the set of common divisors of $A$ is finite, it follows that it has a greatest element, and this is the $\gcd$ of $A$.

If, however, you've defined $\gcd$ as a common divisor $d$ such that every common divisor $d'$ satisfies $d' \mid d$, then there's still some work to do.

Lemma 1: For all $a,b,c \in \mathbb{Z}$, if $\gcd(a,b)=1$ and $a \mid c$ and $b \mid c$, then $ab \mid c$.

You should be able to prove this lemma. This is relevant.

Let the maximum of $\{d_1,\dots d_n\}$ be $d$.

Lemma 2: $d$ is a $\gcd$ of $A$.

Proof: Suppose, for contradiction, that the set of $d_k$, $1 \leq k \leq n$ such that $d_k \not\mid d$ is a nonempty set. Then, by the well-ordering of $\mathbb{N}$, this set has a least element. Call it $d_j$.

Note that since $1 \mid d$, $d_j \neq 1$. We know that every pair of integers in $\mathbb{Z}$ has a $\gcd$, so we can let $g=\gcd(d_j, d)$.

If $g\neq 1$, then $d_j/g <d_j$ is a smaller element of the set of $d_k$ that do not divide $d$. But $d_j$ was supposed to be the smallest element. Contradiction.

If $g=1$, then consider the number $d_j \cdot d$. By Lemma 1, this number divides every element of $A$, and so is a common divisor of $A$. But $d_j \neq 1 \Rightarrow d_j > 1$, so $d_j \cdot d > d$. This contradicts the assumption that $d$ was the maximum of the set of common divisors.

Therefore, the set of common divisors of $A$ that do not divide $d$ is the empty set. This means $d$ is a $\gcd$ of $A$.

As a side note, I'm not sure how useful it is to see the set of linear combinations of the $d_i$ as a subgroup of $(\mathbb{Z},+)$. Isn't it always the trivial subgroup? Isn't the set of linear combinations of the $d_i$ always just $\mathbb{Z}$? $1$ will always be in the set of $d_i$ ...

• I just assumed, that there are finitely many common divisors, since every common divisor $D$ is a divisor of some $a\in A$ and $|D|\leq a$. The side note is so true, how stupid of me, that I didn't realize that. There goes my idea... . I still am baffled though by the proof in the book... – Stefan Perko Dec 21 '14 at 10:39