Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

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

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.