Number theoryDifficulty 6.1National OlympiadProve itIreland
Find the smallest number with exactly 2020 distinct positive divisors. You should include 1 and the number as divisors.
Solution
The divisors of an integer n with prime factorisation n=p1e1⋅p2e2⋯pkek are all of the form p1f1⋅p2f2⋯pkfk, where 0≤fi≤ei. Hence, the number of positive divisors of n is equal to (e1+1)(e2+1)⋯(ek+1) and for each prime number pi that divides n, we have ei+1≥2. We are looking for the smallest n for which (e1+1)(e2+1)⋯(ek+1)=2020. Because 2020=22⋅5⋅101, n can have at most 4 different prime divisors. We will consider, one after the other, the cases k=1,2,3,4.
k = 4. The four factors ei+1 must be 2,2,5,101, hence the ei are 1,1,4,100. To make the number as small as possible, we pair the big ei with the smallest primes possible. This gives n=2100⋅34⋅51⋅71<2100+8+3+3=2114.
k = 3. The set of three factors ei+1 must be either {4,5,101}, or {2,10,101}, or {2,5,202}, or {2,2,505}. Again, pairing the larger powers with the smaller primes, we get the following possibilities: 2100⋅34⋅53>2100+4+6=2110 2100⋅39⋅51>2100+9+2=2111 2201⋅34⋅51>2201 2504⋅31⋅51>2504 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 2114, so both exponents, e1 and e2, must be less than 57, otherwise result will be at least 257⋅357>2114. One of the two factors ei+1 of 2020 must be larger than 2020>44, so we are looking for a factor of 2020 between 44 and 58. From the prime factorisation of 2020 we see that there is no factor in this range.
k = 1. The smallest possibility with one factor is 22019, which is way too big. We are left with three candidates: 2100⋅34⋅5⋅7, 2100⋅34⋅53 2100⋅39⋅5 and need to decide which is the smallest. We can take out a common factor of 2100⋅34⋅5 and compare 7,52,35 and find the first is the smallest. Thus 2100⋅34⋅5⋅7 is the smallest number with exactly 2020 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.