# Prove that there will always be two integers selected that have a common divisor larger than 1.

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.

• To get the best possible answers, you should explain what your thoughts on the problem are. That way, people won't tell you stuff you already know, and they can write answers at an appropriate level; also, people tend to be more willing to help if you show that you've tried the problem yourself. Lastly, some may consider your post rude because it is phrased as a command, not a request for help, so please consider rewriting it. – Zev Chonoles Aug 6 '13 at 2:17

## 3 Answers

Let's try to build a set of $11$ numbers no two of which have a common divisor greater than $1$. We will see that we must fail.

We can use at most one of the $14$ numbers $2.4.6.8.\dots,28$. So we need at least $10$ numbers chosen from the $14$ odd numbers.

We can have at most one of the $5$ numbers $3.9.15.21.27$.

That leaves $9$ numbers not yet mentioned, from which we must select $9$. So if we have successfully avoided using two even numbers, and $2$ numbers divisible by $3$, we must among others select $5$ and $25$. But these have a common divisor greater than $1$.

Hint: It suffices to show that you will select two numbers that have a single common prime factor. How many primes are there between $1$ and $29$?

There are only 9 primes $\{2, 3, 5, 7, 11, 13, 17, 19, 23\}$ less than 29. Every number greater than 1 and less than 29 must have at least one of these primes as a factor. Then any list of 11 numbers greater than 0 and less than 29 must have a repeated prime.