Question

(a) We select 11 positive integers that are less than 29 at random.Prove that there will always be two integers selected that have a common divisor larger than 1.

(b) Is the statement of part (a) true if we only select ten integers that are less than 29? (Discrete Math - Pigeon-Hole Principle)

Answer 1

(a) The pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item.

Now let us choose those positive integers less than 29 who doesn't have a common divisor larger than 1.

So they are all prime numbers along with 1 ={1,2,3,5,7,11,13,17,19,23} these are only 10 integers which have common divisor only 1 if we include any other integer then that integer will not prime and hence its common divisor is larger than 1.

Hence in set of 11 integers there are always two integers whose common divisor is larger 1.

(b) Yes it is true for 10 integers as we already show in above part (a).