, 2015

Number theory Difficulty 4.9 AIME Prove it Romania

Determine all positive integers $n$ such that all positive integers less than or equal to $n$ and prime to $n$ are pairwise coprime.

Solution

Notice that $5$ is the first index $k$ such that $p_1 \cdots p_{k-1} > p_k^2$ . Now, if $p_1 \cdots p_{k-1} > p_k^2$ for some index $k \ge 5$ , then $p_1 \cdots p_{k-1}p_k > p_k^3 > 4p_k^2 > p_{k+1}^2$ , by the Bertrand-Tchebysheff theorem, so $p_1 \cdots p_{k-1} > p_k^2$ for all indices $k \ge 5$ .

Consequently, $m \le 4$ , so $n < p_4^2 = 49$ . Examination of the possible cases quickly yields the required numbers: $1, 2, 3, 4, 6, 8, 12, 18, 24, 30$ .

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 and solution reproduced as published; topic and difficulty added by this site.