Olympiad Maths Prep

Library / /44 of 60

Number theory Difficulty 6.4 National olympiad Prove it Ukraine

Let 1<d1<d2<<dl1<dl<n1 < d_1 < d_2 < \ldots < d_{l-1} < d_l < n denote divisors of composite natural number nn, that is not a square of prime number, l2l \ge 2. For which nn are there natural numbers aa, bb and NN, that satisfy the conditions: d1+d2=Nad_1 + d_2 = N^a and dl1+dl=Nbd_{l-1} + d_l = N^b?

Solution

Notice, that from conditions of the task, it follows, that d1dl=d2dl1=nd_1 \cdot d_l = d_2 \cdot d_{l-1} = n. Using this equality and first equality from conditions, it is possible to rewrite the second equality from the task:
Nb=dl1+dl=nd2+ndl=n(d1+d2)d1d2=nNad1d2 or n=d1d2Nba. N^b = d_{l-1} + d_l = \frac{n}{d_2} + \frac{n}{d_l} = \frac{n(d_1+d_2)}{d_1d_2} = \frac{nN^a}{d_1d_2} \text{ or } n = d_1d_2N^{b-a}.

Apart from that, if b=ab=a, then d1+d2=Na=Nb=dl1+dld_1+d_2 = N^a = N^b = d_{l-1} + d_l, so d1=dl1d_1 = d_{l-1}; d2=dld_2 = d_l. Then the number needed has four divisors, or exactly two proper divisors. There are two forms of such numbers: n=pqn = pq, where p,qp, q are prime numbers, or n=p3n = p^3, where pp is prime. So, we can consider only case b>ab > a.

Consider two cases.

1. Let NN be odd number. Then from equality d1+d2=Nad_1 + d_2 = N^a we have, that sum d1+d2d_1 + d_2 is odd number, then from these divisors there is exactly one even, another is odd. So it is obvious, that d1=2d_1 = 2, as it is the least even divisor. Then d2=Na2d_2 = N^a - 2 must be prime number. Let d2=Na2=pd_2 = N^a - 2 = p, then Na=p+2N^a = p + 2. So, n=2pNban = 2 \cdot p \cdot N^{b-a}.

a) If NN is not prime number, then as Np+2N \le p+2, it has prime divisor qp+2q \le p+2. Obviously, qpq \ne p, and so q<pq < p. But this means, that for b>ab > a number n=2pNban = 2 \cdot p \cdot N^{b-a} is divisible by q<p=d2q < p = d_2, and then number pp can not be d2d_2. We get contradiction.

b) If NN is prime number, then for a>1a > 1 we get, that it follows from equality Na=p+2N^a = p+2, that N<p+2N < p+2, then it is proper divisor of number nn, less than pp, that is impossible. So, a=1a=1, i.e. numbers pp and N=p+2N = p+2 is pair of twin primes. And then b1\forall b \ge 1 we have, that number n=2p(p+2)b1n = 2 \cdot p \cdot (p+2)^{b-1} is solution. Really, dl1=2(p+2)b1d_{l-1} = 2(p+2)^{b-1}, dl=p(p+2)b1d_l = p(p+2)^{b-1} and dl1+dl=2(p+2)b1+p(p+2)b1=(p+2)b=Nbd_{l-1} + d_l = 2(p+2)^{b-1} + p(p+2)^{b-1} = (p+2)^b = N^b.

2. Let NN be even number. As n=d1d2Nabn = d_1d_2N^{a-b}, then nn is also even, i.e. d1=2d_1 = 2.
Then as d1=2d_1 = 2, then d2=4d_2 = 4, as sum of two the least divisors is even. Then Na=6N^a = 6. Then N=6N = 6, a=1a = 1, thus n=246b1n = 2 \cdot 4 \cdot 6^{b-1}. If b>a=1b > a = 1, then number 3 is divisor of number nn, then d2=3d_2 = 3 – contradiction. Thus b=a=1b = a = 1.

Looking for a route rather than 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.