Chinese remainder theorem I am looking for a simple proof to show that given a countable set of natural numbers $C$ that is closed under addition and whose gcd is 1, there exists two elements $c_1, c_2 \in C$ such that $\gcd(c_1, c_2)=1$.
I used the Chinese remainder theorem, but my proof is about half a page and I was wondering if there is a shorter one.
 A: Because $\gcd(C)=1$ there are $a_1,a_2,\ldots,a_n\in C$ such that $\gcd(a_1,\ldots,a_n)=1$.  Thus there are integers $m_1,\ldots m_n$ such that $m_1a_1+\cdots m_na_n=1$.  Let $\{i_1,\ldots,i_p\}\subset\{1,\ldots,n\}$ be those indices corresponding to positive coefficients $m_{i_k}$ and $\{j_1,\ldots,j_q\}$ those corresponding to negative coefficients $m_{j_k}$.  Because $C$ is closed under addition, $c_1=\sum_{k=1}^pm_{i_k}a_{i_k}$ and $c_2=\sum_{k=1}^q-m_{j_k}a_{j_k}$ are in $C$, and $c_1-c_2=1$.
A: (as requested)
Suppose on the contrary that $t_1 \equiv t_2 \equiv 0 \pmod p$ where $p = \gcd(t_1, t_2) > 1$.
Then, there must be a $t_3 \not\equiv 0 \pmod p$ otherwise all elements are divisible by $p > 1$, which is a contradiction.
Let $t_1 = pq$ and $t_2 = pr$.
By the Chinese remainder theorem, for all $s \ge qr$, there are $c_1, c_2 \in \mathbb{Z}$ such that 
$
s = c_1q + c_2r
$.
Let $s = p^a$ where $a \in \mathbb{N}$ is chosen so that $p^a \ge qr$.
Then,
$
c_1t_1 + c_2t_2 = c_1pq + c_2pr = p(c_1q + c_2r) = ps  = p^{a+1}.
$
Hence $\gcd(c_1t_1 + c_2t_2, t_3) = 1$ since the prime factorization of $c_1t_1 + c_2t_2$ consists of $p^{a+1}$ and $t_3$ is relatively prime to $p$.
Since $C$ is closed under addition, $c_1t_1 + c_2t_2\in C$.  Thus, it and $t_3$ are the two elements that have g.c.d. 1.
