Maths Olympiad Prep

Library / /4 of 52

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Romania

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

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.

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.