Maths Olympiad Prep

Library / Danube Mathematical Competition /7 of 28

Danube Mathematical Competition, 2015

Number theory Difficulty 4.9 AIME Prove it Romania

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

Solution

Notice that 55 is the first index kk such that p1⋯pk−1>pk2p_1 \cdots p_{k-1} > p_k^2. Now, if p1⋯pk−1>pk2p_1 \cdots p_{k-1} > p_k^2 for some index k≥5k \ge 5, then p1⋯pk−1pk>pk3>4pk2>pk+12p_1 \cdots p_{k-1}p_k > p_k^3 > 4p_k^2 > p_{k+1}^2, by the Bertrand-Tchebysheff theorem, so p1⋯pk−1>pk2p_1 \cdots p_{k-1} > p_k^2 for all indices k≥5k \ge 5.

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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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