Six Distinct Positive Integers

Book: A Walk through Combinatorics

Problem

A student wrote six distinct positive integers on the board, and pointed out that none of them had a prime factor larger than 10. Prove that there are two integers on the board that have a common prime divisor. Could we make the same conclusion if in the first sentence we replaced "six" by "five"?

Solution

Only possible prime divisors are 2, 3, 5, 7.

There are six numbers, so at least two of them will share the same prime divisor based on the Pigeonhole Principle

Same if there were five numbers.