Maths Olympiad Prep

Library / /330 of 383

Number theory Difficulty 9.0 Shortlist Prove it IMO

Determine all positive, composite integers nn that satisfy the following property: if the positive divisors of nn are 1=d1<d2<<dk=n1=d_{1}<d_{2}<\cdots<d_{k}=n, then did_{i} divides di+1+di+2d_{i+1}+d_{i+2} for every 1ik21 \leqslant i \leqslant k-2.

Solution

Answer: n=prn=p^{r} is a prime power for some r2r \geqslant 2.

Solution 1. It is easy to see that such an n=prn=p^{r} with r2r \geqslant 2 satisfies the condition as di=pi1d_{i}=p^{i-1} with 1ik=r+11 \geqslant i \geqslant k=r+1 and clearly
pi1pi+pi+1 p^{i-1} \mid p^{i}+p^{i+1}
Now, let us suppose that there is a positive integer nn that satisfies the divisibility condition of the problem and that has two different prime divisors pp and qq. Without loss of generality, we assume p<qp<q and that they are the two smallest prime divisors of nn. Then there is a positive integer jj such that
d1=1, d2=p, , dj=pj1, dj+1=pj, dj+2=q d_{1}=1,\ d_{2}=p,\ \ldots,\ d_{j}=p^{j-1},\ d_{j+1}=p^{j},\ d_{j+2}=q
and it follows that
dkj1=nq, dkj=npj, dkj+1=npj1, , dk1=np, dk=n d_{k-j-1}=\frac{n}{q},\ d_{k-j}=\frac{n}{p^{j}},\ d_{k-j+1}=\frac{n}{p^{j-1}},\ \ldots,\ d_{k-1}=\frac{n}{p},\ d_{k}=n
Thus
dkj1=nqdkj+dkj+1=npj+npj1=npj(p+1) \begin{equation*} d_{k-j-1}=\frac{n}{q} \left\lvert\, d_{k-j}+d_{k-j+1}=\frac{n}{p^{j}}+\frac{n}{p^{j-1}}=\frac{n}{p^{j}}(p+1)\right. \tag{1} \end{equation*}
This gives pjq(p+1)p^{j} \mid q(p+1), which is a contradiction since gcd(p,p+1)=1\operatorname{gcd}(p, p+1)=1 and pqp \neq q.

Solution 2. Since didk+1i=nd_{i} d_{k+1-i}=n, we have the equivalence:
dki1dki+dki+1ndi+2ndi+1+ndi d_{k-i-1}\left|d_{k-i}+d_{k-i+1} \Longleftrightarrow \frac{n}{d_{i+2}}\right| \frac{n}{d_{i+1}}+\frac{n}{d_{i}}
We multiply both sides by didi+1di+2d_{i} d_{i+1} d_{i+2} and cancel the nn's to get
didi+1didi+2+di+1di+2 d_{i} d_{i+1} \mid d_{i} d_{i+2}+d_{i+1} d_{i+2}
Hence,
didi+1di+2 \begin{equation*} d_{i} \mid d_{i+1} d_{i+2} \tag{2} \end{equation*}
Moreover, by the condition of the problem,
didi+1(di+1+di+2)=di+12+di+1di+2 d_{i} \mid d_{i+1}\left(d_{i+1}+d_{i+2}\right)=d_{i+1}^{2}+d_{i+1} d_{i+2}
Combining this with (2) we get that didi+12d_{i} \mid d_{i+1}^{2} for all 1ik21 \leqslant i \leqslant k-2.
Let d2=pd_{2}=p be the smallest prime divisor of nn. By induction on ii we prove that pdip \mid d_{i} for all 2ik12 \leqslant i \leqslant k-1. The base case d2=pd_{2}=p is obvious. Let us suppose that pdjp \mid d_{j} for some 2jk22 \leqslant j \leqslant k-2. Then we have that
pdjdj+12pdj+1 p\left|d_{j}\right| d_{j+1}^{2} \Longrightarrow p \mid d_{j+1}
as pp is prime, which completes the induction. This implies that nn has to be a prime power, as otherwise there would be another prime qq that divides nn and we would get that pqp \mid q which is obviously false.
We finally check that the powers of pp satisfy the condition in the statement of the problem as in Solution 1.

Solution 3. We start by proving the following claim:
Claim. didi+1d_{i} \mid d_{i+1} for every 1ik11 \leqslant i \leqslant k-1.
Proof. We prove the Claim by induction on ii; it is trivial for i=1i=1 because d1=1d_{1}=1. Suppose that 2ik12 \leqslant i \leqslant k-1 and the Claim is true for i1i-1, i.e. di1did_{i-1} \mid d_{i}. By the induction hypothesis and the problem condition, di1did_{i-1} \mid d_{i} and di1di+di+1d_{i-1} \mid d_{i}+d_{i+1}, so di1di+1d_{i-1} \mid d_{i+1}.
Now consider the divisors dki=ndi+1,dki+1=ndi,dki+2=ndi1d_{k-i}=\frac{n}{d_{i+1}}, d_{k-i+1}=\frac{n}{d_{i}}, d_{k-i+2}=\frac{n}{d_{i-1}}. By the problem condition,
dki+1+dki+2dki=ndi+ndi1ndi+1=di+1di+di+1di1 \frac{d_{k-i+1}+d_{k-i+2}}{d_{k-i}}=\frac{\frac{n}{d_{i}}+\frac{n}{d_{i-1}}}{\frac{n}{d_{i+1}}}=\frac{d_{i+1}}{d_{i}}+\frac{d_{i+1}}{d_{i-1}}
is an integer. We conclude that di+1di\frac{d_{i+1}}{d_{i}} is an integer, so didi+1d_{i} \mid d_{i+1}.
By the Claim, nn cannot have two different prime divisors because the smallest one would divide the other one. Hence, nn must be a power of a prime, and powers of primes satisfy the condition of the problem as we saw in Solution 1.

Solution 4. We present here a more technical way of finishing Solution 1 after obtaining (1). We let vp(m)v_{p}(m) denote the pp-adic valuation of mm. Notice that vp(n/q)=vp(n)v_{p}(n / q)=v_{p}(n) as gcd(p,q)=1\operatorname{gcd}(p, q)=1 and that
vp(npj(p+1))=vp(n)j v_{p}\left(\frac{n}{p^{j}}(p+1)\right)=v_{p}(n)-j
as gcd(p,p+1)=1\operatorname{gcd}(p, p+1)=1. But (1) implies
vp(n)=vp(n/q)vp(npj(p+1))=vp(n)j v_{p}(n)=v_{p}(n / q) \leqslant v_{p}\left(\frac{n}{p^{j}}(p+1)\right)=v_{p}(n)-j
which is a contradiction. Thus nn has only one prime divisor as desired.

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.