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

• Are you sure this is what you want to prove? If you mean the set must be infinite, take for example 6,10,15,6^2,6^3,6^4,.... – Jonas Meyer Nov 3 '10 at 3:00
• I will update the question. (This problem is a part of a larger problem and I forgot the conditions that I'd used.) – Neil G Nov 3 '10 at 3:03
• Could you give a brief outline of the proof you did using the Chinese rem. th.? – Weltschmerz Nov 3 '10 at 3:30
• Yes, I will add it as a solution. – Neil G Nov 3 '10 at 3:33
• I have added it. Please let me know if it's correct. – Neil G Nov 3 '10 at 4:28

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

• How do you justify the second sentence? – Neil G Nov 3 '10 at 4:51
• Let $G=\{t_1a_1+\cdots+t_na_n:t_k\in\mathbb{Z}\}$ and let $d$ be the smallest positive element of $G$. If $m$ is in $G$, use division with remainder to write $m=qd+r$ with $0\leq r\lt d$. Since $r=m-qd$ is in $G$, $r=0$ by choice of $d$. Hence $d$ divides every element of $G$ including $a_1,\ldots,a_n$, which means $d=1$. (This would more generally produce the gcd of a set of integers.) – Jonas Meyer Nov 3 '10 at 5:09

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