Maths Olympiad Prep

Library / /56 of 75

Number theory Difficulty 5.7 AIME, harder Prove it Italy

Problem:
What is the smallest positive integer that has exactly 15 divisors?

Solution

Solution:
The answer is 144144. Suppose that n=p1a1pkakn = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}} is the prime factorization of nn, with p1<p2<<pkp_{1} < p_{2} < \cdots < p_{k} all distinct and ai>0a_{i} > 0 for i=1,,ki = 1, \ldots, k. A positive integer dd is a divisor of nn if and only if its prime factorization is of the form d=p1b1pkbkd = p_{1}^{b_{1}} \cdots p_{k}^{b_{k}} with 0b1a1,,0bkak0 \leq b_{1} \leq a_{1}, \ldots, 0 \leq b_{k} \leq a_{k} (the exponent 00 is also allowed because not all prime factors of nn necessarily have to appear in the factorization of dd as well: for example, if all the bib_{i} are equal to 00, one obtains the divisor d=1d = 1). The possible choices of dd thus correspond to the possible choices of its factorization, namely a1+1a_{1} + 1 choices for the exponent b1b_{1} (all the integers 0,1,,a10, 1, \ldots, a_{1}), ..., ak+1a_{k} + 1 choices for the exponent bkb_{k}. Combining these choices in all possible ways, one obtains that the number nn has exactly (a1+1)(ak+1)(a_{1} + 1) \cdot \cdots \cdot (a_{k} + 1) divisors.

To have exactly 15=3515 = 3 \cdot 5 divisors, there are thus only the following possibilities:

(i) k=1k = 1, a1=14a_{1} = 14 hence n=p114n = p_{1}^{14}. The smallest positive integer of this type is evidently 214=163842^{14} = 16384.

(ii) k=2k = 2, a1=2a_{1} = 2, a2=4a_{2} = 4 hence n=p12p24n = p_{1}^{2} p_{2}^{4}. The smallest positive integer of this type is evidently 2234=3242^{2} 3^{4} = 324.

(iii) k=2k = 2, a1=4a_{1} = 4, a2=2a_{2} = 2 hence n=p14p22n = p_{1}^{4} p_{2}^{2}. The smallest positive integer of this type is evidently 2432=1442^{4} 3^{2} = 144.

Therefore the number sought is 144144.

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 translated into English from it; metadata (topic, difficulty) added by this project.