Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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