# Two coprime numbers in an infinite set of nonnegative integers

Suppose that we have an infinite set of nonnegative integers $L$. I'm trying to prove that one of these two conditions is true:

1. There exist coprime integers $x,y\in L$.

2. There exists some integer $k$ such that for every $x\in L$, $k|x$.

Is it true or not? If yes, how can I prove it?

-

No it is not true try the infinite set $\{2^n \cdot 3, 3\cdot5,2 \cdot 5 \}$

The condition that $k|x$ for every $x$ in the set is rather strong as in order two numbers to not be co prime is just to share a prime.

Therefore if we could find $3$ integers which pairwise share a prime but they do not share one all the three(i.e. $\mathrm{g.d.c.(n_1,n_2,n_3)}=1$) we would be done, as $k|a_i \Rightarrow k|\mathrm{g.d.c.(n_1,n_2,n_3)}=1$ and for the infinite part we could take the powers of one of them for example $n_1^n$.

Often sometimes it would be usefull to think of the natural numbers of the following way $H : \mathbb{N } \to \mathrm{P(\mathbb{N}})$ where $H(n)=H(p_1^{a_1}\cdotp_2^{a_2}\cdot\ldots\cdot p_k^{a_k})=\{p_1,p_2,\ldots,p_n\}$ This if a good formulation of the problem. Notice this mapping is surjective.

Two numbers $n_1,n_2$ are not comprime iff $H(n_1)\bigcap H(n_2) \not = \emptyset$. And the condition $(2)$ is translated $\bigcap H(n_x)\not = \emptyset$.

So in order to find a counter-example you can find it thinking in sets. That means find three sets $A_i$, $|A_i \bigcap A_j|=1$ and $A_1 \bigcap A_2 \bigcap A_3= \emptyset$. And then you would go back to integers $\bigcup H^{-1}(A_i)$. And it is easy that find such sets.

-
the first element is redundant :-) – mau Mar 29 '13 at 13:54
thank you @mau shall I remove it? – clark Mar 29 '13 at 13:59
@clark Thanks, I was trying to find such an example (: – Random Mar 29 '13 at 14:02
@Clark yes, I think it would be better for people who will read the thread in the future. – mau Mar 29 '13 at 14:12

Hint $\$ It suffices to find a nonempty finite counterexample $\,L,\,$ i.e. a primitive set with all pairs noncoprime. Then $\ n\in L\:\Rightarrow\:L\cup \{n^2,n^3,n^4,\ldots\}\$ is an infinite counterexample.

-