Maths Olympiad Prep

Library / /7 of 17

Number theory Difficulty 4.9 AIME Prove it Bulgaria

Find all natural numbers nn for which the number of positive divisors of LCM(1,2,,n)\text{LCM}(1, 2, \dots, n) is a power of 2.

Solution

For each prime pp, the numbers of the interval n[p2,p3)n \in [p^2, p^3) are not solutions, because the degree of pp in the decomposition of the LCM is 2 and so contributes by a factor of 3 to the number of divisors. Therefore this number is not a power of 2. From Bertrand's postulate for a prime pp there is a prime qq with p<q<2pp < q < 2p, respectively p2<q2<4p2<p3<q3p^2 < q^2 < 4p^2 < p^3 < q^3 for p5p \ge 5; also 32<52<33<533^2 < 5^2 < 3^3 < 5^3. Therefore, each interval [p2,p3)[p^2, p^3) and [q2,q3)[q^2, q^3) for consecutive primes 3p<q3 \le p < q intersects. We obtained that n<9n < 9 and a direct check shows that only n=1,2,3n = 1, 2, 3 and 88 are solutions. \square

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.