How to identify pigeon and pigeon hole in this question?

Question

Twenty numbers, each greater than 1, are picked from the set {1, 2, 3, . . . , 70} of the first seventy natural numbers. Prove that amongst the twenty numbers picked it is guaranteed that two of them, say a and b have a common factor greater than 1.

I assume that those 20 picked numbers are my pigeons, and 2 numbers with gcd > 1 are my pigeon holes.

If I am correct, I am still unsure of how to find the number of my pigeon holes.

Thanks.

Answer 1

There are 19 prime numbers in $[1,70]$ range. Let's say they are $p_1,p_2,...,p_{19}$. Now, let's categorize everything into 19 groups (these are pigeon holes): 1st group with numbers that are divisible by $p_1$, 2nd numbers divisible by $p_2$, and so on (some numbers can be in multiple groups). Now, since you have 20 numbers (pigeons), then some two of them will in one group, so they both will be divisible by some $p$.