# Proving that there are relatively prime elements (Posa problem) [duplicate]

This question already has an answer here:

How to prove that for each $n+1$ an element from the set $\{1,2,3,4,\ldots,2n-1,2n\}$ there are two relatively prime elements between them

-
Can you rephrase the question? I'm not sure what you're asking. –  Alex Becker Mar 24 '13 at 15:49
I'm sorry: I don't know what a rational prime element is. –  1015 Mar 24 '13 at 15:52
While "rational prime" does have a meaning, I suspect you mean relatively prime. –  Thomas Andrews Mar 24 '13 at 15:55
I suspect the question is: given any $n+1$ elements of that set, prove that there must be two of them that are relatively prime. –  Thomas Andrews Mar 24 '13 at 15:57
@Thomas Andrews yes you are right I meant to say relatively prime.Thank you –  user68282 Mar 24 '13 at 15:57
add comment

## marked as duplicate by Pete L. Clark, Davide Giraudo, Arkamis, Amzoti, Dennis GulkoMar 24 '13 at 18:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 3 Answers

Hint $\$ Show by pigeonhole that subset has a neighboring pair $\rm\:n,\, n\!+\!1,\:$ which is coprime

-
add comment

Group the $2n$ integers into $n$ sets: $\{1,2\}, \{3,4\},\cdots,\{2n-1,2n\}$. The elements in each set are coprime. Now use the pigeonhole principle.

-
add comment

Hint: Let $a,b,c$ be elements in a subset $S$ of $\{1,\dotsc,2n\}$ of cardinality $n+1$. Suppose that there is a prime $p$ which divides $a$ and $b$, but not $c$. If another prime $q$ divides $c$ but not $a$ or $b$ you are done. Otherwise in a similar way you can prove that there is a prime $r$ which divides every element in $S$...

-
add comment