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!