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.

  • $\begingroup$ 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,.... $\endgroup$ – Jonas Meyer Nov 3 '10 at 3:00
  • $\begingroup$ I will update the question. (This problem is a part of a larger problem and I forgot the conditions that I'd used.) $\endgroup$ – Neil G Nov 3 '10 at 3:03
  • $\begingroup$ Could you give a brief outline of the proof you did using the Chinese rem. th.? $\endgroup$ – Weltschmerz Nov 3 '10 at 3:30
  • $\begingroup$ Yes, I will add it as a solution. $\endgroup$ – Neil G Nov 3 '10 at 3:33
  • $\begingroup$ I have added it. Please let me know if it's correct. $\endgroup$ – 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$.

  • $\begingroup$ How do you justify the second sentence? $\endgroup$ – Neil G Nov 3 '10 at 4:51
  • $\begingroup$ 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.) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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