Maths Olympiad Prep

Track / Stage 7 / 136 of 300 #2016 of 2444

Problem 2016

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.5 Prove it NMO Selection Tests for BMO and IMO · Romania

Determine all positive integers nn such that all positive integers less than nn and coprime to nn are powers of primes.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Notice that 66 is the first index kk such that p1p2pk2>pk1pkp_1p_2 \cdots p_{k-2} > p_{k-1}p_k. Now, if p1p2pk2>pk1pkp_1p_2 \cdots p_{k-2} > p_{k-1}p_k for some index k6k \ge 6, then (by Bertrand-Tchebysheff) p1p2pk1>pk12pk>2pk12pk>pkpk+1p_1p_2 \cdots p_{k-1} > p_{k-1}^2p_k > 2p_{k-1} \cdot 2p_k > p_kp_{k+1}, so p1p2pk2>pk1pkp_1p_2 \cdots p_{k-2} > p_{k-1}p_k for all indices k6k \ge 6.
Consequently, m5m \le 5, r=pmp5=11r = p_m \le p_5 = 11, qp4=7q \le p_4 = 7, and n<qrp4p5=711=77n < qr \le p_4p_5 = 7 \cdot 11 = 77. Examination of the integers less than 7777 quickly yields the required numbers: 2,3,4,5,6,8,9,10,12,14,18,20,24,30,42,602, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60.

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