# sets and relatively prime integers

• Nov 29th 2009, 02:37 PM
keityo
sets and relatively prime integers
If $\displaystyle S$ is any set of $\displaystyle n + 1$ integers selected from $\displaystyle 1, 2, 3,\cdot\cdot\cdot,2n + 1$,

prove that $\displaystyle S$ contains two relatively prime integers.
Prove that the result does not hold if $\displaystyle S$ contains only $\displaystyle n$ integers.

I think that the pigeonhole principle might be a way to prove this, but I don't know to determine what are the pigeons and what are the pigeonholes.

Thanks for the help!
• Nov 29th 2009, 03:10 PM
Plato
Quote:

Originally Posted by keityo
If $\displaystyle S$ is any set of $\displaystyle n + 1$ integers selected from $\displaystyle 1, 2, 3,\cdot\cdot\cdot,2n + 1$,
prove that $\displaystyle S$ contains two relatively prime integers.
Prove that the result does not hold if $\displaystyle S$ contains only $\displaystyle n$ integers.

You need to notice that if $\displaystyle \{a,b\}\subseteq \{1,2,\cdots,2n+1\}$ then $\displaystyle \gcd(a,b)\le n-1$.
• Nov 29th 2009, 03:24 PM
keityo
Why is http://www.mathhelpforum.com/math-he...bc1d3c07-1.gif then http://www.mathhelpforum.com/math-he...b7a63d68-1.gif true?

I just had an idea: if $\displaystyle S$ has only n integers, then the set $\displaystyle {2,4,6,\cdot\cdot\cdot,2n}$ will have n integers, and all will be not relatively prime, which proves the second statement.

If $\displaystyle S$ has n+1 integers, then one of the integers must be odd because there can only be n even numbers in the set $\displaystyle {1,2,...,2n + 1}$ Thus, 2 and that odd number will be relatively prime, which proves the second statement.

Is this proof ok?
Thanks again.
• Nov 29th 2009, 04:52 PM
Bruno J.
Use the pigeon-hole principle! Amongst the following $\displaystyle n$ sets, there must be one containing two of your numbers :

$\displaystyle \{1,2\}, \{3,4\},\hdots \{2n-1, 2n, 2n+1\}$

Now just remark that any two integers which lie in the same part of this partition are relatively prime.
• Nov 29th 2009, 06:04 PM
chiph588@
For your second part: $\displaystyle \{2,4,6,8,...,2n\}$.