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