Take the 2-minute tour ×
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.

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

share|improve this question
4  
Can you rephrase the question? I'm not sure what you're asking. –  Alex Becker Mar 24 '13 at 15:49
1  
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
1  
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 Gulko Mar 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

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

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

share|improve this answer
add comment

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