Suppose that S is a subset of {1, 2,..., 2n} of size n+1.
(a) Show that S must contain two integers a and b such that gcd(a,b)=1.
(b) Show that S must contain two integers c and d such that c divides d.
I think you use the pigeonhole principle for part b, but I'm not sure how...please help