Maths Olympiad Prep

Library / /16 of 27

Number theory Difficulty 6.2 National olympiad Prove it Brazil

A positive integer is bold iff it has 88 positive divisors that sum up to 32403240. For example, 20062006 is bold because its 88 positive divisors, 11, 22, 1717, 3434, 5959, 118118, 10031003 and 20062006, sum up to 32403240. Find the smallest positive bold number.

Solution

Let n=p1α1pkαkn = p_1^{\alpha_1} \cdots p_k^{\alpha_k}. Then 8=(α1+1)(αk+1)8 = (\alpha_1 + 1) \cdots (\alpha_k + 1), and 3240=p1α1+11p11pkαk+11pk13240 = \frac{p_1^{\alpha_1+1}-1}{p_1-1} \cdots \frac{p_k^{\alpha_k+1}-1}{p_k-1}. Hence there are three cases:
(a) 8=α1+1    n=p78 = \alpha_1 + 1 \implies n = p^7.
(b) 8=(α1+1)(α2+1)    n=p1p238 = (\alpha_1 + 1)(\alpha_2 + 1) \implies n = p_1 p_2^3.
(c) 8=(α1+1)(α2+1)(α3+1)    n=p1p2p38 = (\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1) \implies n = p_1 p_2 p_3.
Then we check σ(n)\sigma(n):
(a) 1+p2++p7=32401 + p^2 + \cdots + p^7 = 3240. We have 2<p<52 < p < 5, so p=3p = 3. But substituting yields no solution.
(b) (p1+1)(p23+p22+p2+1)=3240    (p1+1)(p2+1)(p22+1)=3240(p_1 + 1)(p_2^3 + p_2^2 + p_2 + 1) = 3240 \iff (p_1 + 1)(p_2 + 1)(p_2^2 + 1) = 3240. First note that if qq is an odd prime then, by Fermat's theorem, p22+10(modq)    1p2q1(1)q12(modq)    q1(modq)p_2^2 + 1 \equiv 0 \pmod{q} \implies 1 \equiv p_2^{q-1} \equiv (-1)^{\frac{q-1}{2}} \pmod{q} \implies q \equiv 1 \pmod{q}. Since 3240=233453240 = 2^3 \cdot 3^4 \cdot 5, the only primes that can divide p22+1p_2^2 + 1 are 22 and 55. This leaves the possibilities p2=2p_2 = 2 and p2=3p_2 = 3, none of which yield a solution.

(c) (p1+1)(p2+1)(p3+1)=3240(p_1+1)(p_2+1)(p_3+1) = 3240. Let's consider some cases.
(c.1) One of the primes pip_i is 22. Suppose that p1=2p_1 = 2. Then (p2+1)(p3+1)=1080    (p2+12)(p3+12)=270(p_2+1)(p_3+1) = 1080 \iff (\frac{p_2+1}{2})(\frac{p_3+1}{2}) = 270.
Let x=p2+12x = \frac{p_2+1}{2} and y=p3+12y = \frac{p_3+1}{2}. Then xy=270xy = 270 is fixed and we want to minimize 2p2p3=2(2x1)(2y1)=82704(x+y)+22p_2p_3 = 2(2x-1)(2y-1) = 8 \cdot 270 - 4(x+y) + 2, that is, we want to maximize x+yx+y. This happens when xy|x-y| is maximum. Since p2p_2 and p3p_3 are primes, the optimal values for xx and yy are x=2x=2 and y=135y=135, that is, p2=3p_2 = 3 and p3=269p_3 = 269, leading to the minimal solution n=1614n = 1614.
(c.2) All primes pip_i are odd. Then (p1+12)(p2+12)(p3+12)=405=335(\frac{p_1+1}{2})(\frac{p_2+1}{2})(\frac{p_3+1}{2}) = 405 = 3^3 \cdot 5. Then one prime, say p1p_1, is equal to 23k51=103k12 \cdot 3^k \cdot 5 - 1 = 10 \cdot 3^k - 1; and since pi+12\frac{p_i+1}{2} cannot be equal to 11, then they must have at least one factor 33 for i=2,3i=2,3; there are only three factors 33, so k=0k=0 or k=1k=1. k=0k=0 is not possible; k=1k=1 yields p1=29p_1 = 29 and (p2+12)(p3+12)=27    p2=5(\frac{p_2+1}{2})(\frac{p_3+1}{2}) = 27 \implies p_2 = 5 and p3=17p_3 = 17, leading to n=2465n = 2465.
Hence the smallest value for nn is 16141614.

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 and solution reproduced as published; topic and difficulty added by this site.