Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes or any two numbers in this subset have a greatest common divisor greater than 1?
There is a beautiful solution for this problem, my teacher told me that it is hard but you don’t have to use anything.
So I am looking for solutions not using well known theorems... thanks!
This is an application of the infinite Ramsey theorem, see https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.