Maths Olympiad Prep

Library / /49 of 82

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

For a positive integer dd, let f(d)f(d) be the smallest positive integer with exactly dd positive divisors. (E.g. f(1)=1f(1) = 1, f(5)=16f(5) = 16, f(6)=12f(6) = 12.)
Prove that for any positive integer kk the number f(2k1)f(2^{k-1}) divides f(2k)f(2^k).

Solution

Let n=p1a1p2a2prar,ai0n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, a_i \ge 0 be the prime factorization of the number nn. Then the number of divisors of nn is (a1+1)(a2+1)(ar+1)(a_1+1)(a_2+1)\cdots(a_r+1).

Let kk be a positive integer and let f(2k)=p1a1p2a2prarf(2^k) = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}. Then ai=2bi1a_i = 2^{b_i} - 1 for some integers bi0b_i \ge 0, i=1,2,,ri = 1, 2, \dots, r and i=1rbi=k\sum_{i=1}^r b_i = k.
Let pi,pjp_i, p_j be any two distinct prime factors of f(2k)f(2^k). If we replace pi2bi1p_i^{2^{b_i}-1} with pi2bi+11p_i^{2^{b_i+1}-1} and pj2bj1p_j^{2^{b_j}-1} with pj2bj11p_j^{2^{b_j-1}-1} in the prime factorization of f(2k)f(2^k) we get a number that also has 2k2^k divisors (as f(2k)f(2^k)) because 2bi+12bj1=2bi2bj2^{b_i+1} \cdot 2^{b_j-1} = 2^{b_i} \cdot 2^{b_j}. Minimality of f(2k)f(2^k) implies
pi2bi1pj2bj1<pi2bi+11pj2bj11, p_i^{2^{b_i}-1} \cdot p_j^{2^{b_j}-1} < p_i^{2^{b_i+1}-1} \cdot p_j^{2^{b_j-1}-1},
or equivalently
pj2bj1<pi2bi.() p_j^{2^{b_j}-1} < p_i^{2^{b_i}}. \qquad (\bullet)
If we allow some of the integers cic_i or bib_i to be zero, we can write f(2k+1)=p12c11p22c21pr2cr1f(2^{k+1}) = p_1^{2^{c_1}-1} p_2^{2^{c_2}-1} \cdots p_r^{2^{c_r}-1}.
Since i=1rci=k+1>k=i=1rbi\sum_{i=1}^r c_i = k+1 > k = \sum_{i=1}^r b_i, there is a positive integer ss such that cs>bsc_s > b_s.
Let tt be a positive integer different than ss. Using ()(\bullet) for the pair (ps,pt)(p_s, p_t), and for the pair (pt,ps)(p_t, p_s) gives
pt2ct>ps2cs1ps2bs>pt2bt1. p_t^{2^{c_t}} > p_s^{2^{c_s}-1} \ge p_s^{2^{b_s}} > p_t^{2^{b_t}-1}.
We conclude ct>bt1c_t > b_t - 1, i.e. ctbtc_t \ge b_t for all t=1,,rt = 1, \dots, r, which implies that f(2k+1)f(2^{k+1}) divides f(2k)f(2^k).

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.