Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad /144 of 201

Ukrainian National Mathematical Olympiad

Number theory Difficulty 6.4 National Olympiad Prove it Ukraine

Let 1<d1<d2<…<dl−1<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, l≥2l \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 dl−1+dl=Nbd_{l-1} + d_l = N^b?

Solution

Notice, that from conditions of the task, it follows, that d1⋅dl=d2⋅dl−1=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=dl−1+dl=nd2+ndl=n(d1+d2)d1d2=nNad1d2 or n=d1d2Nb−a. 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=dl−1+dld_1+d_2 = N^a = N^b = d_{l-1} + d_l, so d1=dl−1d_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=Na−2d_2 = N^a - 2 must be prime number. Let d2=Na−2=pd_2 = N^a - 2 = p, then Na=p+2N^a = p + 2. So, n=2⋅p⋅Nb−an = 2 \cdot p \cdot N^{b-a}.

a) If NN is not prime number, then as N≤p+2N \le p+2, it has prime divisor q≤p+2q \le p+2. Obviously, q≠pq \ne p, and so q<pq < p. But this means, that for b>ab > a number n=2⋅p⋅Nb−an = 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 ∀b≥1\forall b \ge 1 we have, that number n=2⋅p⋅(p+2)b−1n = 2 \cdot p \cdot (p+2)^{b-1} is solution. Really, dl−1=2(p+2)b−1d_{l-1} = 2(p+2)^{b-1}, dl=p(p+2)b−1d_l = p(p+2)^{b-1} and dl−1+dl=2(p+2)b−1+p(p+2)b−1=(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=d1d2Na−bn = 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=2⋅4⋅6b−1n = 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.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.