# A Property of Additive Subsets of $\mathbb{Z}^+$ with GCD 1

I encountered the following fact:

Suppose $A$ is any set of non-negative integers which is closed under addition and has greatest common divisor 1. Then $A$ must contain all but finitely many non-negative integers.

The proof presented relied on a lemma that effectively shows that there exists an $m=m(A)$ such that for all $n\in A$ with $n\geq m$ on has that $n$ can be written as a linear combination of elements of $A$ with nonnegative coefficients. The proof of this lemma is not entirely difficult but, I was wondering if there is an especially elegant one or two line proof of the fact above?

• What do you mean by "Has greatest common divisor 1"? Who has that? Obviously not all elements of $A$, as if $a\in A\,$ , then also $a+a=2a\in A$ , and $\,(a,2a)\neq 1\,$... – DonAntonio Jun 4 '12 at 1:43
• @DonAntonio: It makes perfect sense to talk about the gcd of a set of numbers; for a PID, it is exactly the generator of the ideal generated by the set. – Arturo Magidin Jun 4 '12 at 2:24
• @Arturo Never heard of that...so if I have $\,A:=\{3,4,8\}\,$ say, then the gcd of $A$ is $\,24\,$ , as $\,\langle 3,4,8\rangle_\mathbb{Z} = 24\mathbb{Z}\leq \mathbb{Z}\,$? , and thus the OP is asking about a set of natural numbers that the ideal generated in the integers by them is $\mathbb{Z}\,$? – DonAntonio Jun 4 '12 at 2:31
• @DonAntonio: What makes you think that the ideal generated by $3$, $4$, and $8$ is generated by $24$? It's generated by $1$, since it contains $4-3$. The gcd of a set of of numbers $\{a_i\}$ is the nonnegative number $d$ that satisfies the universal definition: it divides each $a_i$, and any common divisor of all $a_i$ divides $d$. In the case of $\mathbb{Z}$ (or any PID) it coincides with a generator of the ideal they generate. That's why we have "pairwise coprime" to refer to a set in which every pair of elements has gcd 1, as opposed to "coprime" to mean the gcd of the whole set is 1. – Arturo Magidin Jun 4 '12 at 2:34
• I was thinking of the ideal $\,3\mathbb{Z}\cap 4\mathbb{Z}\cap 8\mathbb{Z}\,$...anyway, then it is always the unit ideal when among the numbers are two coprime...right? – DonAntonio Jun 4 '12 at 2:39

If $x,y\in A$, $x<y$ and $\gcd(x,y)=1$ (such a pair must exist) then $S=\{y,2y,\ldots,xy\}\subset A$ covers all residue classes modulo $x$ so $S+\{kx|k\in \mathbb{Z}^+\}$ includes every number $\ge xy$.

(This is short, but I don't know if you'd consider it "especially elegant," particularly if you need convincing of the "such a pair must exist" claim.)

Edit: Here's a proof for the missing step.

Let $\gcd(x_1,x_2,\ldots,x_n)=1$ for $x_i \in A, n>2$. Then by Bezout's identity there are $u,v\in \mathbb{Z}$ with $ux_1+vx_2=\gcd(x_1,x_2)$. Choose $k$ so that $kx_3\ge\max(-u,-v)$, then $$x_2' = (kx_3+u)x_1+(kx_3+v)x_2 \in A \\ x_2' \equiv \gcd(x_1,x_2) \pmod{x_3}\\ \gcd(x_2',x_3) = \gcd(x_1,x_2,x_3) \\ \gcd(x_2',x_3,\ldots,x_n)=\gcd(x_1,x_2,\ldots,x_n)=1$$ Thus given a set of $n>2$ elements of $A$ with $\gcd=1$ we can find a set with $n-1$ elements with $\gcd=1$. $A$ must contain a finite such set, so we can repeat this procedure to reduce the size until we have a pair of relatively prime elements.

In case it's necessary, to see that $A$ must have a finite set of elements with $\gcd=1$, choose any element $x$ with prime factorization $x=\prod p_i^{a_i}$. By definition $A$ must contain a $y_i$ such that $p_i \nmid y_i$, otherwise $p_i \mid \gcd(A)$. Then $\gcd(\{x\}\cup\{y_i\}_i)=1$.

Now this is probably as complicated as your original proof...

• What if $A$ is all the positive integer sums of $\{6,10,15\}\,$, as written in one of the comments above? What such pair must exist in this case? – DonAntonio Jun 4 '12 at 3:40
• 6 and 25 works. – Zander Jun 4 '12 at 3:44
• Of course, one can be a multiple of "first" ones. Thanx – DonAntonio Jun 4 '12 at 3:55
• Or even $16=10+6$ and $15$. – Arturo Magidin Jun 4 '12 at 5:10
• Thank you, while I think that this is of the same flavor as the solution I'm thinking of, your rephrasing is what I'm looking for. – Alex R. Jun 5 '12 at 1:31