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!
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?