Can any help me how to solve this problem with clear solution please.?

Two positive integers p and q are RELATIVE PRIME if the largest integer that divides both p and q is 1. Let n be a positive integer and let A={1,2,....2n-1,2n}. Prove that any subset A' of A with |A'|=n+1 must contain two integers that are relatively prime.Can any help me how to solve this problem with clear solution please.?
Induction's the way to go:





If the theorem is true for an integer n, then consider the possibilities for n+1:





A(n+1)={1,2,....2n-1,2n,2n+1,2n+2} has the two additional elements 2n+1 and 2n+2 that are not in A(n).





Now consider what A'(n+1), by definition containing n+2 elements, can consist of:





1. Neither 2n+1 nor 2n+2 are in A'.


2. Only one of 2n and 2n+1 is in A'.


3. Both 2n and 2n+1 are in A'.





In case (1), A' is contained in A(n), so any subset of A' containing n+1 elements fulfills the requirements of the theorem for n, and therefore two integers that are relatively prime must exist in that set.





In case (2), eliminating that element that is either 2n+1 or 2n+2 leaves a set with n+1 elements contained in A(n), so again, that set must contain two integers that are relatively prime.





In case (3), A' contains both 2n+1 and 2n+2 - consecutive integers. These must be relatively prime, because otherwise they'd both be divisible by the same prime number p: 2n+1 = ip, 2n+2 = jp. Subtracting, we get





(2n+2) - (2n+1) = 1 = jp - ip = (j-i)p.





But this can't be true if p%26gt;1, since j-i is also an integer.





So in all cases, if the theorem is true for n, it must also be true for n+1.





And of course it is true for n=1 since A={1,2} and A' = {1,2} (no other choice), and 1 and 2 are relatively prime.





QED