Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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|cite|improve this question

marked as duplicate by Pete L. Clark, Davide Giraudo, Emily, 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.

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

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

share|cite|improve this answer

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

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

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