Maths Olympiad Prep

Library / /3 of 17

Number theory Difficulty 5.5 AIME, harder Prove it Argentina

For nNn \in \mathbb{N} let D2(n)D_2(n) (respectively D3(n)D_3(n)) denote the number of divisors of nn that are perfect squares (respectively perfect cubes). Prove that there is an nn such that D2(n)=999D3(n)D_2(n) = 999D_3(n).

Solution

For aNa \in \mathbb{N} denote u(a)=[a2]u(a) = \left[ \frac{a}{2} \right], v(a)=[a3]v(a) = \left[ \frac{a}{3} \right]. If n=p1a1pkakn = p_1^{a_1} \cdots p_k^{a_k} is the prime factorization of nNn \in \mathbb{N}, it is straightforward that D2(n)=(u(a1)+1)(u(ak)+1)D_2(n) = (u(a_1)+1)\cdots(u(a_k)+1), D3(n)=(v(a1)+1)(v(ak)+1)D_3(n) = (v(a_1)+1)\cdots(v(a_k)+1).

Define a1=2998a_1 = 2 \cdot 998 and set ai=2v(ai1)a_i = 2v(a_{i-1}) for i2i \ge 2. (Only the first several terms of the infinite sequence (ai)(a_i) will be used.) With this definition we have u(ai)=998u(a_i) = 998 and u(ai)=v(ai1)u(a_i) = v(a_{i-1}) for i2i \ge 2.

Note also that v(ai)=23v(ai1)<v(ai1)v(a_i) = \lfloor \frac{2}{3}v(a_{i-1}) \rfloor < v(a_{i-1}) if v(ai1)>0v(a_{i-1}) > 0. Thus the sequence (v(ai))(v(a_i)) decreases, so its terms are 00 for sufficiently large ii.

Take the first index kk such that v(ak)=0v(a_k) = 0 and define n=p1a1pkakn = p_1^{a_1} \cdots p_k^{a_k}. Because u(ai)=v(ai1)u(a_i) = v(a_{i-1}) for i2i \ge 2,

D2(n)=(998+1)(u(a2)+1)(u(ak)+1)=999(v(a1)+1)(v(ak1)+1). D_2(n) = (998+1)(u(a_2)+1)\cdots(u(a_k)+1) = 999(v(a_1)+1)\cdots(v(a_{k-1})+1).

In addition D3(n)=(v(a1)+1)(v(ak1)+1)(v(ak)+1)D_3(n) = (v(a_1)+1)\cdots(v(a_{k-1})+1)(v(a_k)+1) equals (v(a1)+1)(v(ak1)+1)(v(a_1)+1)\cdots(v(a_{k-1})+1) since the last factor v(ak)+1v(a_k)+1 is 11 due to v(ak)=0v(a_k)=0. Therefore D2(n)=999D3(n)D_2(n) = 999D_3(n).

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.