Maths Olympiad Prep

Library / /13 of 42

Number theory Difficulty 5.6 AIME, harder Prove it Romania

Let nn be a composite positive integer and let 1=d1<d2<d3<<dk=n1 = d_1 < d_2 < d_3 < \dots < d_k = n be the divisors of nn, where k3k \ge 3. Assume that all the equations di+2x22di+1x+di=0d_{i+2}x^2 - 2d_{i+1}x + d_i = 0, for i{1,2,,k2}i \in \{1, 2, \dots, k-2\} have real solutions. Prove that n=pk1n = p^{k-1} for some prime number pp.

Solution

4di+124di+2di0di+1didi+2di+1() 4d_{i+1}^2 - 4d_{i+2} \cdot d_i \ge 0 \Leftrightarrow \frac{d_{i+1}}{d_i} \ge \frac{d_{i+2}}{d_{i+1}} \quad (*)
for any i{1,2,,k2}i \in \{1, 2, \dots, k-2\}.
As d2d_2 is the smallest proper divisor of nn, it means that the number nd2\frac{n}{d_2} is the greatest proper divisor of nn, so nd2=dk1\frac{n}{d_2} = d_{k-1}. We have:
nd2=dk1=i=1k2di+1dii=1k2di+2di+1=nd2. \frac{n}{d_2} = d_{k-1} = \prod_{i=1}^{k-2} \frac{d_{i+1}}{d_i} \ge \prod_{i=1}^{k-2} \frac{d_{i+2}}{d_{i+1}} = \frac{n}{d_2}.
It follows that all inequalities (*) turn into equalities.
Thus, di+12=di+2did_{i+1}^2 = d_{i+2} \cdot d_i for any i{1,2,,k2}i \in \{1, 2, \dots, k-2\}. It follows that the numbers 1=d1,d2,d3,,dk=n1 = d_1, d_2, d_3, \dots, d_k = n (in this order) are consecutive terms of a geometric progression of ratio d2d_2, so n=d2k1n = d_2^{k-1}.
The lowest proper divisor of the composite number nn is a prime number pp, so d2=pd_2 = p, and n=pk1n = p^{k-1}.

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.