2
$\begingroup$

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.

  • 0
    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,....2010-11-03
  • 0
    I will update the question. (This problem is a part of a larger problem and I forgot the conditions that I'd used.)2010-11-03
  • 0
    Could you give a brief outline of the proof you did using the Chinese rem. th.?2010-11-03
  • 0
    Yes, I will add it as a solution.2010-11-03
  • 0
    I have added it. Please let me know if it's correct.2010-11-03

2 Answers 2

3

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

  • 0
    How do you justify the second sentence?2010-11-03
  • 0
    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.)2010-11-03
0

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