Maths Olympiad Prep

Library / /6 of 9

Number theory Difficulty 6.0 AIME, harder Prove it Austria

Determine all composite positive integers nn with the following property: If 1=d1<d2<<dk=n1 = d_1 < d_2 < \dots < d_k = n are all the positive divisors of nn, then
(d2d1):(d3d2)::(dkdk1)=1:2::(k1). (d_2 - d_1) : (d_3 - d_2) : \dots : (d_k - d_{k-1}) = 1 : 2 : \dots : (k-1).

Solution

Since nn is a composite number, we have k3k \ge 3.
Let d2=pd_2 = p be the smallest prime that divides nn. We show by induction that
dj=j(j1)2p(j2)(j+1)2,j=1,2,,k. d_j = \frac{j(j-1)}{2}p - \frac{(j-2)(j+1)}{2}, \quad j = 1, 2, \dots, k.

This is clearly true for j=1j = 1 and the induction step follows from djdj1=(j1)(d2d1)=(j1)(p1)d_j - d_{j-1} = (j-1)(d_2 - d_1) = (j-1)(p-1) and 1+2+3++(j1)=j(j1)21 + 2 + 3 + \dots + (j-1) = \frac{j(j-1)}{2}.
If we apply this formula to dk1=np=dkd2d_{k-1} = \frac{n}{p} = \frac{d_k}{d_2} and multiply by 2p2p, we get
(k1)(k2)p2(k3)kp=k(k1)p(k2)(k+1)(k1)(k2)p22(k2)kp+(k2)(k+1)=0(k1)p22kp+(k+1)=0. \begin{aligned} & (k-1)(k-2)p^2 - (k-3)kp = k(k-1)p - (k-2)(k+1) \\ \Leftrightarrow \quad & (k-1)(k-2)p^2 - 2(k-2)kp + (k-2)(k+1) = 0 \\ \Leftrightarrow \quad & (k-1)p^2 - 2kp + (k+1) = 0. \end{aligned}
The solutions of this quadratic equation are p=1p = 1 and p=k+1k1=1+2k1p = \frac{k+1}{k-1} = 1 + \frac{2}{k-1}. Since both options are at most 2, the only possibility is p=2p = 2, k=3k = 3 and n=4n = 4. Since n=4n = 4 has the required property, this is the only 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 and solution reproduced as published; topic and difficulty added by this site.