Maths Olympiad Prep

Library / /338 of 348

Number theory Difficulty 5.3 AIME, harder Find the answer

Find the smallest positive integer nn such that the divisors of nn can be partitioned into three sets with equal sums.

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

Solution

I claim the answer is 120. First, note that 120=2335120=2^{3} \cdot 3 \cdot 5, so the sum of divisors is (1+2+4+8)(1+3)(1+5)=1546=360(1+2+4+8)(1+3)(1+5)=15 \cdot 4 \cdot 6=360. Thus, we need to split the divisors into groups summing to 120 . But then we can just take {120},{20,40,60},{1,2,3,4,5,6,8,10,12,15,24,30}\{120\},\{20,40,60\},\{1,2,3,4,5,6,8,10,12,15,24,30\}. Thus, 120 works. Now we need to show 120 is the lowest. Let s(n)s(n) be the sum of divisors. Since nn will be in one of the piles, we need s(n)3ns(n) \geq 3 n. First, we claim that nn must have at least 3 distinct prime divisors. Surely, if it had 2 distinct prime divisors, say pp and qq, so that n=paqbn=p^{a} q^{b}, then the sum of divisors is (1+p+p2++pa)(1+q+q2++qb)=paqb(1+1p++1pa)(1+1q++1qb)\left(1+p+p^{2}+\ldots+p^{a}\right)\left(1+q+q^{2}+\ldots+q^{b}\right)=p^{a} q^{b}\left(1+\frac{1}{p}+\ldots+\frac{1}{p^{a}}\right)\left(1+\frac{1}{q}+\ldots+\frac{1}{q^{b}}\right) However, the expression 1+1p++1pa1+\frac{1}{p}+\ldots+\frac{1}{p^{a}} is maximized when pp is minimized, and further, as aa is finite must be at most 111p=pp1\frac{1}{1-\frac{1}{p}}=\frac{p}{p-1}. Thus, the sum of divisors is less than paqbpp1qq1n232=3np^{a} q^{b} \frac{p}{p-1} \frac{q}{q-1} \leq n \cdot 2 \cdot \frac{3}{2}=3 n Thus, nn can't have 2 distinct prime divisors and must have at least 3 distinct prime divisors. As we already discovered 120 works, we need not worry about 4 distinct prime divisors, as the value of nn would be at least 2357=2102 \cdot 3 \cdot 5 \cdot 7=210. We now work through the numbers with 3 distinct divisors. If 2 is not one of them, then the only number that works is 105=357105=3 \cdot 5 \cdot 7, which has a sum of divisors that is not large enough. Therefore, 2 must be a prime divisor of nn. Additionally, if 3 is not a divisor, then our options are 2572 \cdot 5 \cdot 7 and 25112 \cdot 5 \cdot 11, which also do not work. Therefore, 3 must also be a prime divisor. Then, if 5 is not a prime divisor, then if nn is 23p2 \cdot 3 \cdot p, it has a sum of divisors of (1+2)(1+3)(1+p)=n3243p+1p(1+2)(1+3)(1+p)=n \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \frac{p+1}{p}, which is only at least 3n3 n if pp is exactly 2 , which is not feasible. Additionally, if we use 222^{2}, then the sum of divisors is (1+2+4)(1+3)(1+p)=n7443pp+1(1+2+4)(1+3)(1+p)=n \cdot \frac{7}{4} \cdot \frac{4}{3} \cdot \frac{p}{p+1}, so p+1p>97p<4.5\frac{p+1}{p}>\frac{9}{7} \Longrightarrow p<4.5, which also can't happen. Further, we can't have 323^{2} be a divisor of nn as 23252 \cdot 3^{2} \cdot 5 is the only value less than 120 with this, and that also does not work. Lastly, we just need to check 233p2^{3} \cdot 3 \cdot p, which has a sum of divisors of (1+2+4+8)(1+3)(1+p)=n15843p+1p=n52pp+1(1+2+4+8)(1+3)(1+p)=n \cdot \frac{15}{8} \cdot \frac{4}{3} \cdot \frac{p+1}{p}=n \cdot \frac{5}{2} \cdot \frac{p}{p+1}, so p=5p=5 and that works. This means that n=120n=120 is the smallest value for which s(n)3ns(n) \geq 3 n, and thus is our answer.

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.