Track / Stage 4 / 63 of 340 #323 of 2000

Problem 323

AMC 12 late, AIME early

Number theory Difficulty 4.7 Prove it XX OBM · Brazil

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

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.