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$ ...

  • $\begingroup$ 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... $\endgroup$ – Stefan Perko Dec 21 '14 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.