Skip to main content
OlympiadHQ

Browse · MathNet

Print

XX OBM

Brazil number theory

Problem

15 positive integers smaller than are relatively prime (no pair has a common factor larger than ). Show that at least one of them must be prime.
Solution
Suppose there are such integers, none prime. If we list the primes in order, the th is . Now let be the smallest prime dividing . Take to be that integer among the which has the largest . Then since is not prime and is its smallest prime factor, we must have . Since all integers are relatively prime, they must all have different s. Hence , so . Contradiction.

Techniques

Prime numbersPigeonhole principle