Maths Olympiad Prep

Library / /152 of 173

Number theory Difficulty 3.1 AMC 10/12 Find the answer

The integer NN is the smallest positive integer that is a multiple of 2024, has more than 100 positive divisors (including 1 and NN), and has fewer than 110 positive divisors (including 1 and NN). What is the sum of the digits of NN?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Throughout this solution, we use the fact that if NN is a positive integer with N>1N>1 and NN has prime factorization p1a1p2a2pmamp_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{m}^{a_{m}} for some distinct prime numbers p1,p2,,pmp_{1}, p_{2}, \ldots, p_{m} and positive integers a1,a2,,ama_{1}, a_{2}, \ldots, a_{m}, then the number of positive divisors of NN including 1 and NN is equal to (1+a1)(1+a2)(1+am)(1+a_{1})(1+a_{2}) \cdots(1+a_{m}). We are told that NN is a positive multiple of 2024. Now, 2024=8253=2311232024=8 \cdot 253=2^{3} \cdot 11 \cdot 23. This means that NN has at least 3 prime factors (namely 2,11 and 23) and that at least one of these prime factors has an exponent of at least 3. Let DD be the number of positive divisors that NN has. We are told that 100<D<110100<D<110. Since D=(1+a1)(1+a2)(1+am)D=(1+a_{1})(1+a_{2}) \cdots(1+a_{m}) and NN has at least 3 prime factors, then DD is a positive integer that can be written as the product of at least 3 positive integers each greater than 2. DD cannot equal 101,103,107101,103,107, or 109, since each of these is prime (and so cannot be written as the product of 3 integers each at least 2). DD also cannot equal 106 because 106=253106=2 \cdot 53 (both 2 and 53 are prime), which means that 106 cannot be written as the product of three integers each greater than 1. The possible values of DD that remain are 102,104,105,108102,104,105,108. We note that 102=2317102=2 \cdot 3 \cdot 17 and 104=2313104=2^{3} \cdot 13 and 105=357105=3 \cdot 5 \cdot 7 and 108=2233108=2^{2} \cdot 3^{3}. Case 1: D=102D=102 Since the prime factors of NN include at least 2,11 and 23, then the prime factorization of NN includes factors of 2a,11b2^{a}, 11^{b} and 23c23^{c} for some positive integers a,ba, b and cc with a3a \geq 3. If a fourth prime power pep^{e} was also a factor of NN, then DD would be divisible by (1+a)(1+b)(1+c)(1+e)(D(1+a)(1+b)(1+c)(1+e) \cdot(D could have more factors if NN had more prime factors.) Since D=102=2317D=102=2 \cdot 3 \cdot 17 has only 3 prime factors, it cannot be written as the product of 4 integers each greater than 1. Thus, NN cannot have a fourth prime factor. This means that N=2a11b23cN=2^{a} 11^{b} 23^{c}, which gives D=(1+a)(1+b)(1+c)=2317D=(1+a)(1+b)(1+c)=2 \cdot 3 \cdot 17. This means that 1+a,1+b1+a, 1+b and 1+c1+c are equal to 2,3 and 17, in some order, and so a,ba, b and cc are equal to 1,2 and 16, in some order. For DD to be as small as possible, the largest exponent goes with the smallest prime, the next largest exponent with the next smallest prime, and so on. (Can you see why this makes NN as small as possible?) Therefore, the smallest possible value of NN in this case is N=216112231=182386688N=2^{16} 11^{2} 23^{1}=182386688. Case 2: D=105D=105 Using a similar argument, we can determine that N=2a11b23cN=2^{a} 11^{b} 23^{c} with 1+a,1+b1+a, 1+b and 1+c1+c equal to 3,5 and 7 in some order, meaning that a,ba, b and cc equal 2,4,62,4,6 in some order. Therefore, the minimum value of NN is this case is N=26114232=495685696N=2^{6} 11^{4} 23^{2}=495685696. Case 3: D=104D=104 Since D=2313D=2^{3} \cdot 13 has 4 prime factors, then NN cannot have more than 4 prime factors. (If NN had 5 or more prime factors, then the product equal to DD would include at least 5 integers, each at least 2.) Therefore, N=2a11b23cN=2^{a} 11^{b} 23^{c} and D=(1+a)(1+b)(1+c)D=(1+a)(1+b)(1+c), or N=2a11b23cpeN=2^{a} 11^{b} 23^{c} p^{e} for some prime p2,11,23p \neq 2,11,23 and D=(1+a)(1+b)(1+c)(1+e)D=(1+a)(1+b)(1+c)(1+e). This means that (1+a)(1+b)(1+c)=2313(1+a)(1+b)(1+c)=2^{3} \cdot 13 or (1+a)(1+b)(1+c)(1+e)=2313(1+a)(1+b)(1+c)(1+e)=2^{3} \cdot 13. In the case that NN has three prime factors, we note that 104=2622=1342104=26 \cdot 2 \cdot 2=13 \cdot 4 \cdot 2 are the only two ways of writing 104 as the product of 3 integers each of which is at least 2. These give corresponding minimum values of N=2251123=8489271296N=2^{25} \cdot 11 \cdot 23=8489271296 and N=21211323=125390848N=2^{12} \cdot 11^{3} \cdot 23=125390848. In the case that NN has four prime factors, then (1+a)(1+b)(1+c)(1+e)=22213(1+a)(1+b)(1+c)(1+e)=2 \cdot 2 \cdot 2 \cdot 13 means that a,b,ca, b, c and ee are 1,1,1,121,1,1,12 in some order. This in turn means that the corresponding smallest possible value of NN is N=21231123=3108864N=2^{12} \cdot 3 \cdot 11 \cdot 23=3108864. We note here that the prime power pep^{e} has become 313^{1} in order to minimize both pp (since p>2p>2 ) and its exponent. Case 4: D=108D=108 Since D=2233D=2^{2} \cdot 3^{3} has 5 prime factors, then NN cannot have more than 5 prime factors. If NN has 5 prime factors, then we need to use the factorization D=22333D=2 \cdot 2 \cdot 3 \cdot 3 \cdot 3. This is not possible, however, because the power 2a2^{a} must have a3a \geq 3 which would mean that one of the five factors of DD would have to be at least 4. If NN has 4 prime factors, then DD must be partitioned as 93229 \cdot 3 \cdot 2 \cdot 2 or 63326 \cdot 3 \cdot 3 \cdot 2 or 43334 \cdot 3 \cdot 3 \cdot 3. (Since two of the prime factors have to be combined, either two 2 s , two 3 s , or a 2 and a 3 are combined.) These give minimum values of N=28321123=582912N=2^{8} \cdot 3^{2} \cdot 11 \cdot 23=582912 and N=253211223=801504N=2^{5} \cdot 3^{2} \cdot 11^{2} \cdot 23=801504 and N=2332112232=4408648N=2^{3} \cdot 3^{2} \cdot 11^{2} \cdot 23^{2}=4408648. If NN has 3 prime factors, then we must use one of the factorizations D=2722D=27 \cdot 2 \cdot 2 or D=1832D=18 \cdot 3 \cdot 2 or D=1233D=12 \cdot 3 \cdot 3 or D=943D=9 \cdot 4 \cdot 3 or D=663D=6 \cdot 6 \cdot 3. These gives corresponding minimum values N=2261123=16978542592N=2^{26} \cdot 11 \cdot 23=16978542592, N=21711223=364773376N=2^{17} \cdot 11^{2} \cdot 23=364773376, N=211112232=131090432N=2^{11} \cdot 11^{2} \cdot 23^{2}=131090432, N=28113232=180249344N=2^{8} \cdot 11^{3} \cdot 23^{2}=180249344, N=25115232=2726271328N=2^{5} \cdot 11^{5} \cdot 23^{2}=2726271328. Combining Cases 1 through 4, the minimum possible value of NN is 582912. The sum of the digits of 582912 is 5+8+2+9+1+2=275+8+2+9+1+2=27.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.