Maths Olympiad Prep

Library / /292 of 462

Number theory Difficulty 6.1 National Olympiad Prove it Ireland

Find the smallest number with exactly 20202020 distinct positive divisors. You should include 11 and the number as divisors.

Solution

The divisors of an integer nn with prime factorisation
n=p1e1p2e2pkek n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}
are all of the form p1f1p2f2pkfkp_1^{f_1} \cdot p_2^{f_2} \cdots p_k^{f_k}, where 0fiei0 \le f_i \le e_i. Hence, the number of positive divisors of nn is equal to (e1+1)(e2+1)(ek+1)(e_1+1)(e_2+1)\cdots(e_k+1) and for each prime number pip_i that divides nn, we have ei+12e_i+1 \ge 2.
We are looking for the smallest nn for which (e1+1)(e2+1)(ek+1)=2020(e_1+1)(e_2+1)\cdots(e_k+1) = 2020. Because 2020=2251012020 = 2^2 \cdot 5 \cdot 101, nn can have at most 44 different prime divisors. We will consider, one after the other, the cases k=1,2,3,4k=1, 2, 3, 4.

k = 4. The four factors ei+1e_i+1 must be 2,2,5,1012, 2, 5, 101, hence the eie_i are 1,1,4,1001, 1, 4, 100. To make the number as small as possible, we pair the big eie_i with the smallest primes possible. This gives
n=2100345171<2100+8+3+3=2114. n = 2^{100} \cdot 3^4 \cdot 5^1 \cdot 7^1 < 2^{100+8+3+3} = 2^{114}.

k = 3. The set of three factors ei+1e_i+1 must be either {4,5,101}\{4, 5, 101\}, or {2,10,101}\{2, 10, 101\}, or {2,5,202}\{2, 5, 202\}, or {2,2,505}\{2, 2, 505\}. Again, pairing the larger powers with the smaller primes, we get the following possibilities:
21003453>2100+4+6=2110 2^{100} \cdot 3^4 \cdot 5^3 > 2^{100+4+6} = 2^{110}
21003951>2100+9+2=2111 2^{100} \cdot 3^9 \cdot 5^1 > 2^{100+9+2} = 2^{111}
22013451>2201 2^{201} \cdot 3^4 \cdot 5^1 > 2^{201}
25043151>2504 2^{504} \cdot 3^1 \cdot 5^1 > 2^{504}
We can reject the last two candidates as being too big. We will return to the first two at the end.

k = 2. With two factors, we are only interested in case where the result will be less than 21142^{114}, so both exponents, e1e_1 and e2e_2, must be less than 5757, otherwise result will be at least 257357>21142^{57} \cdot 3^{57} > 2^{114}. One of the two factors ei+1e_i+1 of 20202020 must be larger than 2020>44\sqrt{2020} > 44, so we are looking for a factor of 20202020 between 4444 and 5858. From the prime factorisation of 20202020 we see that there is no factor in this range.

k = 1. The smallest possibility with one factor is 220192^{2019}, which is way too big. We are left with three candidates:
21003457, 2^{100} \cdot 3^4 \cdot 5 \cdot 7,
21003453 2^{100} \cdot 3^4 \cdot 5^3
2100395 2^{100} \cdot 3^9 \cdot 5
and need to decide which is the smallest. We can take out a common factor of 21003452^{100} \cdot 3^4 \cdot 5 and compare 7,52,357, 5^2, 3^5 and find the first is the smallest. Thus 210034572^{100} \cdot 3^4 \cdot 5 \cdot 7 is the smallest number with exactly 20202020 distinct positive divisors.

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.