Maths Olympiad Prep

Library / /19 of 22

Number theory Difficulty 6.9 National Olympiad Prove it Italy

Problem:

Let nn be a positive integer and let 1=d1<d2<d3<<dk=n1 = d_{1} < d_{2} < d_{3} < \ldots < d_{k} = n be its positive divisors, ordered by size. It is known that k4k \geq 4 and that d32+d42=2n+1d_{3}^{2} + d_{4}^{2} = 2n + 1.

a. Find all possible values of kk.

b. Find all possible values of nn.

Solution

Solution:

a.
First, we observe that d4d_{4} cannot be less than or equal to n\sqrt{n}, because otherwise d32+d42d_{3}^{2} + d_{4}^{2} would be less than (n1)2+n2<2n+1(\sqrt{n} - 1)^{2} + \sqrt{n}^{2} < 2n + 1, while we know it equals 2n+12n + 1. Likewise, if d3d_{3} were greater than or equal to n\sqrt{n} we would have d32+d42>2n+1d_{3}^{2} + d_{4}^{2} > 2n + 1, again a contradiction: hence d3<n<d4d_{3} < \sqrt{n} < d_{4}, and in particular n\sqrt{n} is not a divisor of nn.

We further observe that if dd is a divisor of nn then so is n/dn / d, and this operation exchanges the divisors greater than n\sqrt{n} with those less than n\sqrt{n}. It follows that nn has as many divisors greater than n\sqrt{n} as divisors less than n\sqrt{n}: since these are 3 by what we have just said, nn has 6 divisors.

b.
First solution
Note that we also have d3d4=nd_{3} d_{4} = n: the smallest divisor greater than n\sqrt{n} (that is, d4d_{4}) equals n/dn / d, where dd is the largest divisor less than n\sqrt{n} (that is, d3d_{3}). From the equation d32+d42=2n+1d_{3}^{2} + d_{4}^{2} = 2n + 1 we then deduce d32+d42=2d3d4+1d_{3}^{2} + d_{4}^{2} = 2 d_{3} d_{4} + 1, that is, (d3d4)2=1(d_{3} - d_{4})^{2} = 1, and hence d4d3=1d_{4} - d_{3} = 1 (since d4>d3d_{4} > d_{3}). The number nn can then be written as n=d3(d3+1)n = d_{3}(d_{3} + 1), and in particular it is even, because one of the two factors d3,d3+1d_{3}, d_{3} + 1 is even. The divisors of nn are therefore 1,2,d3,d3+1,n2,n1, 2, d_{3}, d_{3} + 1, \frac{n}{2}, n.

Since the divisors of d3d_{3} are also divisors of nn, either d3d_{3} has no divisors other than 1 and d3d_{3} (and hence is prime), or its only nontrivial divisor is 2 (and hence d3=4d_{3} = 4). In the second case we have n=d3(d3+1)=45=20n = d_{3}(d_{3} + 1) = 4 \cdot 5 = 20, and otherwise we repeat the same reasoning with the divisors of d3+1d_{3} + 1: if d3d_{3} is prime then d3+1d_{3} + 1 is even, and on the other hand it cannot have nontrivial divisors other than 2, so d3+1=4d_{3} + 1 = 4 and n=d3(d3+1)=12n = d_{3}(d_{3} + 1) = 12.

Finally, one easily checks that n=12n = 12 and n=20n = 20 are indeed solutions (in the two cases we have d32+d42=32+42=25=212+1d_{3}^{2} + d_{4}^{2} = 3^{2} + 4^{2} = 25 = 2 \cdot 12 + 1, d32+d42=16+25=41=220+1d_{3}^{2} + d_{4}^{2} = 16 + 25 = 41 = 2 \cdot 20 + 1), and by what we have already said these are the only ones.

Second solution
Exactly one of d3d_{3} and d4d_{4} is even: if d3,d4d_{3}, d_{4} had the same parity, then d32+d42=2n+1d_{3}^{2} + d_{4}^{2} = 2n + 1 would be even, which it clearly is not. Moreover d3d4=nd_{3} d_{4} = n: the smallest divisor greater than n\sqrt{n} (that is, d4d_{4}) equals n/dn / d, where dd is the largest divisor less than n\sqrt{n} (that is, d3d_{3}). The divisors of nn are therefore 1,2,d3,n/d3,n/2,n1, 2, d_{3}, n / d_{3}, n / 2, n.

Since the divisors of d3d_{3} are also divisors of nn, either d3d_{3} has no divisors other than 1 and d3d_{3} (and hence is prime), or its only nontrivial divisor is 2 (and hence d3=4d_{3} = 4). Similarly, the only possible divisors of d4d_{4} are 1,2,d31, 2, d_{3}, but if d3d_{3} divided d4d_{4} then d3d_{3} would divide d32,d42d_{3}^{2}, d_{4}^{2} and nn and hence, by subtraction, would divide d32+d422n=1d_{3}^{2} + d_{4}^{2} - 2n = 1, absurd. So d4d_{4} too is either prime or equal to 4. If d4=4d_{4} = 4, then we have 2=d2<d3<d4=42 = d_{2} < d_{3} < d_{4} = 4 and hence d3=3d_{3} = 3, n=12n = 12. Otherwise d3=4d_{3} = 4, d4d_{4} is a prime pp, and n=4pn = 4p. The equation of the problem then becomes 42+p2=8p+14^{2} + p^{2} = 8p + 1, whose solutions are p=5,p=3p = 5, p = 3. Since p=d4>d3=4p = d_{4} > d_{3} = 4, the only possibility is p=5p = 5, which gives the other solution n=20n = 20.

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.