Maths Olympiad Prep

Library / /41 of 73

Number theory Difficulty 5.9 AIME, harder Prove it Brazil

a. Show a positive integer not greater than 10001000 with at least 2020 positive divisors.

b. Does there exist a positive integer not greater than 1100011000 with at least 200200 positive divisors?

Solution

a. For example, 900=223252900 = 2^2 \cdot 3^2 \cdot 5^2, which has (2+1)(2+1)(2+1)=27(2+1) \cdot (2+1) \cdot (2+1) = 27 positive divisors.

b. No, there doesn't. Let nn be a number with at least 200200 divisors. If the ii-th divisor is dd, then the ii-th to last divisor is nd\frac{n}{d}. Let mm be the 100100th divisor. So m100m \ge 100 and nm>m    n>m2=10000\frac{n}{m} > m \iff n > m^2 = 10000. Close enough, but how do we fix this? First notice that if 9797, 9999 and 100100 are all divisors of nn, then nlcm(97,99,100)>11000n \ge \text{lcm}(97, 99, 100) > 11000. So the key observation is considering the 9898th, 9999th and 100100th divisors. Let k,k, \ell and mm be such divisors. Notice that if m105m \ge 105 we are done because then n>m2=11025>11000n > m^2 = 11025 > 11000. So 98k<<m10498 \le k < \ell < m \le 104. But gcd(x,y)xy\text{gcd}(x, y) \le |x - y| implies that nlcm(k,,m)km(k)(m)(mk)9899100(10498)32>11000n \ge \text{lcm}(k, \ell, m) \ge \frac{k \cdot \ell \cdot m}{(\ell-k)(m-\ell)(m-k)} \ge \frac{98 \cdot 99 \cdot 100}{(104-98) \cdot 3^2} > 11000. Here we used the fact that if x+y2tx+y \le 2t then xyt2xy \le t^2 applied to x=k,y=mx = \ell - k, y = m - \ell and t=3t = 3.

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.