0

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.

Charlie Xu
  • 11

1 Answers1

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$.

Daniyar Aubekerov
  • 933
  • 4
  • 13
  • Thanks for your answer. It makes things much more clearer now. However, I'm still a bit confused about why those 19 groups are the pigeon holes. How can you justify formally that they are the pigeon holes? – Charlie Xu Apr 29 '20 at 10:40
  • In addition, there are only 11 prime divisors in [1, 70]. Why can you have 19 groups? – Charlie Xu Apr 29 '20 at 11:13