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.
Brazilian Mathematical Olympiad
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.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.