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?
 A: 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...
