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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.