Maths Olympiad Prep

Library / /28 of 140

Number theory Difficulty 4.7 AIME Prove it Brazil

15 positive integers smaller than 19981998 are relatively prime (no pair has a common factor larger than 11). Show that at least one of them must be prime.

Solution

Suppose there are 1515 such integers, none prime. If we list the primes in order, the 1515th is p15=47p_{15} = 47. Now let p(n)p(n) be the smallest prime dividing nn. Take NN to be that integer nn among the 1515 which has the largest p(n)p(n). Then since NN is not prime and p(n)p(n) is its smallest prime factor, we must have Np(n)2N \geq p(n)^2. Since all 1515 integers are relatively prime, they must all have different p(n)p(n)s. Hence p(n)=p15p(n) = p_{15}, so Np152>1998N \geq p_{15}^2 > 1998. 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.