Maths Olympiad Prep

Library / /2 of 4

Number theory Difficulty 5.9 AIME, harder Prove it Romania

Determine all integers n2n \ge 2, having at least four positive divisors, with the property that for any two distinct divisors d1d_1 and d2d_2 of nn, such that 1<d1<d2<n1 < d_1 < d_2 < n, the number d2d1d_2 - d_1 is also a divisor of nn.
Lucian Petrescu

Solution

There are three solutions: n=6n = 6, n=8n = 8 and n=12n = 12.

First, notice that if nn is odd, all its divisors are also odd, so if d1d_1 and d2d_2 are two divisors such that 1<d1<d2<n1 < d_1 < d_2 < n, then d2d1d_2 - d_1 is even, so d2d1nd_2 - d_1 \nmid n. Therefore, nn is even.

Consider n=2abn = 2^a \cdot b, where a,bN1a, b \in \mathbb{N}_{\ge 1} and bb is odd.
If b=1b = 1, then n=2an = 2^a, with aNa \in \mathbb{N}^*. For a{1,2}a \in \{1, 2\} there are no solutions, and for a4a \ge 4, choosing d1=2a3d_1 = 2^{a-3} and d2=2a1d_2 = 2^{a-1}, it follows that d2d1=32a3nd_2 - d_1 = 3 \cdot 2^{a-3} \nmid n, a contradiction. Consequently, a=3a = 3, so n=8n = 8. It's trivial to see that n=8n = 8 is a solution of the problem.

For b3b \ge 3 we have two cases.
If a=1a = 1, then n=2bn = 2b. Choose d1=2d_1 = 2 and d2=bd_2 = b; we obtain b22bb - 2 \mid 2b, so b22b2(b2)=4b - 2 \mid 2b - 2(b - 2) = 4. Since bb is odd, we infer that b=3b = 3, so n=6n = 6, which is a solution.

If a2a \ge 2, choose d1=2ad_1 = 2^a and d2=2a1bd_2 = 2^{a-1} \cdot b; we obtain 2a1(b2)2ab2^{a-1}(b-2) \mid 2^a \cdot b, so b22bb - 2 \mid 2b. Since bb is odd, similarly it follows that b=3b = 3. Therefore, n=2a3n = 2^a \cdot 3.
Choose now d1=3d_1 = 3 and d2=2ad_2 = 2^a; it results that 2a32a32^a - 3 \mid 2^a \cdot 3, so 2a32a33(2a3)=92^a - 3 \mid 2^a \cdot 3 - 3 \cdot (2^a - 3) = 9, from which we obtain a=2a = 2. Hence, n=12n = 12 and we easily verify that it is a solution.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.