Thread: sets and relatively prime integers

If is any set of integers selected from ,

prove that contains two relatively prime integers.
Prove that the result does not hold if contains only 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!

Originally Posted by keityo

If is any set of integers selected from ,
prove that contains two relatively prime integers.
Prove that the result does not hold if contains only integers.

You need to notice that if then .

Why is then true?

I just had an idea: if has only n integers, then the set will have n integers, and all will be not relatively prime, which proves the second statement.

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

Is this proof ok?
Thanks again.

Use the pigeon-hole principle! Amongst the following sets, there must be one containing two of your numbers :



Now just remark that any two integers which lie in the same part of this partition are relatively prime.

For your second part: .