IMO 2023 Problem 1
The condition relates consecutive divisors in increasing order.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m14s
Problem
Determine all composite integers $n>1$ that satisfy the following property: if $d_1,d_2,\dots,d_k$ are all the positive divisors of $n$ with $1=d_1<d_2<\dots<d_k=n$, then $d_i$ divides $d_{i+1}+d_{i+2}$ for every $1\le i \le k-2$.
Exploration
The condition relates consecutive divisors in increasing order. A first check on prime powers is natural. If $n=p^r$, then the divisors are
$$1,p,p^2,\dots,p^r,$$
and
$$p^{i-1}\mid p^i+p^{i+1}=p^i(1+p),$$
so every prime power satisfies the condition.
The real question is whether any integer with at least two distinct prime factors can satisfy it.
Let $p<q$ be the two smallest prime divisors of such an integer. If $p^a| n$, then the initial divisors are
$$1,p,p^2,\dots,p^a,q,\dots$$
because every divisor smaller than $q$ must be a power of $p$.
The same description can be read backwards. The largest divisors are
$$\frac n q,\frac n{p^a},\frac n{p^{a-1}},\dots,\frac np,n.$$
The promising place to use the divisibility condition is near the end of the divisor list. Applying it at the divisor $\frac n q$ yields
$$\frac n q\mid \frac n{p^a}+\frac n{p^{a-1}},$$
which simplifies to
$$q\mid p+1.$$
Since $q>p$, this forces $(p,q)=(2,3)$. The remaining task is to show that even this exceptional pair cannot occur. Applying the same condition one step farther to the right produces
$$3\mid 2+1,$$
again, and then the next step gives
$$3\mid 2+1,$$
repeatedly. Eventually the condition reaches the divisor $1$, which would force all divisors smaller than $3$ to be powers of $2$. This suggests that every divisor not divisible by $3$ is a power of $2$, and the first divisor involving $3$ causes a contradiction. Thus no integer with two distinct prime factors survives.
The core insight is that the condition near the top of the divisor list reflects information about the smallest prime divisors of $n$.
Problem Understanding
We are given a composite integer $n$ and the increasing sequence of all positive divisors
$$1=d_1<d_2<\cdots<d_k=n.$$
The requirement is that
$$d_i\mid d_{i+1}+d_{i+2}$$
for every index $1\le i\le k-2$.
This is a classification problem, so it is of Type A. We must determine exactly which composite integers satisfy the condition.
The answer is:
$$\boxed{\text{all prime powers }n=p^r\text{ with }r\ge 2.}$$
The intuitive reason is that for a prime power the divisors form a geometric progression, and the divisibility relation becomes immediate. If two distinct primes occur, then the ordering of divisors forces a rigid pattern at both the beginning and the end of the divisor list, and the condition links those two patterns in a way that is impossible.
Proof Architecture
We shall prove the following statements.
Lemma 1
If $n=p^r$ with $r\ge2$, then the condition holds.
The proof is a direct computation using the divisor list $1,p,\dots,p^r$.
Lemma 2
Assume $n$ satisfies the condition and has at least two distinct prime divisors. Let $p<q$ be the two smallest prime divisors of $n$, and let $p^a| n$. Then
$$q\mid p+1.$$
The proof uses the divisor condition at the divisor $\frac n q$.
Lemma 3
Under the assumptions of Lemma 2, one must have $(p,q)=(2,3)$.
This follows immediately from $q\mid p+1$ and $q>p$.
Lemma 4
No integer having the two distinct prime divisors $2$ and $3$ satisfies the condition.
The proof repeats the argument behind Lemma 2 at successive positions and derives a contradiction.
The difficult direction is the exclusion of integers with at least two distinct prime factors. The most delicate point is translating the divisor ordering into the precise descriptions of the first and last segments of the divisor list.
Solution
We prove first that every prime power satisfies the condition.
Lemma 1
If $n=p^r$ with $r\ge2$, then $n$ satisfies the required property.
Proof
The positive divisors of $n$ are
$$1,p,p^2,\dots,p^r.$$
For $1\le i\le r-1$,
$$d_i=p^{i-1},\qquad d_{i+1}=p^i,\qquad d_{i+2}=p^{i+1}.$$
Hence
$$d_{i+1}+d_{i+2} =p^i+p^{i+1} =p^i(1+p),$$
which is divisible by $p^{i-1}=d_i$.
Thus the condition holds for every index. ∎
This establishes that every prime power is a solution; merely checking a few initial divisors would not suffice because the condition must hold for all indices.
Now assume that $n$ satisfies the condition and has at least two distinct prime divisors.
Let $p<q$ be the two smallest prime divisors of $n$, and let $p^a| n$.
Since every divisor smaller than $q$ is a power of $p$, the beginning of the divisor list is
$$1,p,p^2,\dots,p^a,q,\dots .$$
Consequently the end of the divisor list is
$$\dots,\frac nq,\frac n{p^a},\frac n{p^{a-1}},\dots,\frac np,n.$$
Lemma 2
Under these assumptions,
$$q\mid p+1.$$
Proof
The divisor
$$\frac nq$$
is immediately followed by
$$\frac n{p^a},\qquad \frac n{p^{a-1}}.$$
Applying the given condition at the index corresponding to $\frac nq$ yields
$$\frac nq \mid \frac n{p^a}+\frac n{p^{a-1}} = \frac n{p^a}(1+p).$$
Dividing by $\frac n{p^a q}$ gives
$$q\mid p+1.$$
This proves the lemma. ∎
This establishes a strong arithmetic restriction; replacing the ordered-divisor argument by a purely congruential one would not identify the crucial factor $q$.
Lemma 3
One has
$$(p,q)=(2,3).$$
Proof
Since $q>p$ and $q\mid p+1$, we have
$$q\le p+1.$$
Together with $q>p$, this forces
$$q=p+1.$$
Two consecutive integers can both be prime only when
$$p=2,\qquad q=3.$$
Hence $(p,q)=(2,3)$. ∎
This establishes that any counterexample must involve the primes $2$ and $3$.
Lemma 4
No integer having the distinct prime divisors $2$ and $3$ satisfies the condition.
Proof
Let $2^a| n$.
As before, the beginning of the divisor list is
$$1,2,2^2,\dots,2^a,3,\dots,$$
and the end is
$$\dots,\frac n3,\frac n{2^a},\frac n{2^{a-1}},\dots,\frac n2,n.$$
Apply the condition at the divisor $\frac n3$. Since $p=2$, the computation of Lemma 2 becomes
$$\frac n3 \mid \frac n{2^a}+\frac n{2^{a-1}} = \frac{3n}{2^a}.$$
Therefore
$$\frac n3\mid \frac{3n}{2^a},$$
which implies
$$2^a\mid 9.$$
Since $2^a$ is a power of $2$, the only possibility is
$$a=0.$$
But $2$ is a prime divisor of $n$, so $a\ge1$. This contradiction shows that no such $n$ exists. ∎
This establishes that an integer satisfying the condition cannot have two distinct prime divisors; omitting the exact divisibility calculation would miss the contradiction.
Having ruled out all integers with at least two distinct prime divisors, every solution must be a prime power. By Lemma 1, every prime power $p^r$ with $r\ge2$ indeed satisfies the condition.
Hence the complete set of solutions is
$$\boxed{{,p^r:\ p\text{ prime},\ r\ge2,}}.$$
Verification of Key Steps
The first delicate step is the description of the initial divisors. Let $p<q$ be the two smallest prime divisors of $n$ and let $p^a| n$. Any divisor smaller than $q$ cannot contain a prime factor other than $p$, because every other prime factor is at least $q$. Hence every divisor below $q$ is a power of $p$. Since $p^{a+1}\nmid n$, the divisors below $q$ are exactly
$$1,p,\dots,p^a.$$
A careless argument could forget to justify why no mixed divisor such as $pr$ appears before $q$.
The second delicate step is the translation of the final divisors. Divisor inversion $d\mapsto n/d$ reverses order. Since the first divisors are
$$1,p,\dots,p^a,q,$$
the last divisors must be
$$\frac nq,\frac n{p^a},\dots,\frac np,n.$$
Without explicitly invoking order reversal, the placement of $\frac nq$ among the largest divisors would be unjustified.
The third delicate step is deriving $2^a\mid9$ when $(p,q)=(2,3)$. Starting from
$$\frac n3\mid \frac{3n}{2^a},$$
there exists an integer $m$ such that
$$\frac{3n}{2^a}=m\frac n3.$$
Cancelling $n$ gives
$$\frac3{2^a}=\frac m3,$$
hence
$$9=m,2^a.$$
Therefore $2^a\mid9$. Forgetting the cancellation argument would leave a gap.
Alternative Approaches
A different route begins from the largest divisors. Let
$$d_{k-2},\ d_{k-1},\ d_k=n$$
be the three largest divisors. Since
$$d_{k-2}\mid d_{k-1}+n$$
and $d_{k-2}\mid n$, one obtains
$$d_{k-2}\mid d_{k-1}.$$
From the structure of divisors, this forces
$$d_{k-1}=p,d_{k-2}$$
for some prime $p$. Repeating the argument inductively yields
$$d_1\mid d_2\mid \cdots \mid d_k.$$
A finite divisor set that is totally ordered by divisibility must come from a prime power, which immediately gives the classification. This approach is elegant but requires a careful induction on the divisor chain. The method used in the main proof reaches the contradiction more directly by exploiting the smallest two prime factors.