Competition problem — Number theory

Library / /6 of 19

Number theory Difficulty 4.7 AIME Prove it Soviet Union

Problem:

Show that if 15 numbers lie between 2 and 1992 and each pair is coprime, then at least one is prime.

Solution

Solution:

Suppose not. Then since $452 = 2025 > 1992$ , each of the numbers must have a prime factor $\leq 43$ . But there are only 14 such primes: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43$ . Hence
there must be two numbers with the same prime factor and they cannot be coprime. 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.