IMO 2009 Problem 1
Testing small cases clarifies the structure.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m57s
Problem
Let $n$ be a positive integer and let $a_1,\ldots,a_k (k\ge2)$ be distinct integers in the set ${1,\ldots,n}$ such that $n$ divides $a_i(a_{i+1}-1)$ for $i=1,\ldots,k-1$. Prove that $n$ doesn't divide $a_k(a_1-1)$.
Author: Ross Atkins, Australia
Exploration
Testing small cases clarifies the structure. For $n=2$, the condition forces each step to satisfy $2 \mid a_i(a_{i+1}-1)$, so if $a_i=1$ then $a_{i+1}$ must be odd, hence $1$. If $a_i=2$ then no restriction is imposed on $a_{i+1}$. Any attempt to form a cycle of distinct elements in ${1,2}$ fails immediately because the propagation forces repetition.
For $n=3$, if $a_i=1$ then $a_{i+1}\equiv 1 \pmod 3$, hence $a_{i+1}=1$, again forcing collapse. If $a_i=2$, then $3 \mid 2(a_{i+1}-1)$ implies $3 \mid (a_{i+1}-1)$, so $a_{i+1}=1$. Any chain rapidly collapses into $1$, preventing distinctness.
These experiments suggest a rigid propagation of prime divisibility: primes dividing $n$ that do not divide $a_i$ enforce strong restrictions on $a_{i+1}-1$, while primes dividing $a_i$ impose no restriction on that prime for the next term. This asymmetry suggests tracking which primes divide each term.
The earlier flawed approach tried to propagate full prime powers into $a_{i+1}-1$, which fails. The correct invariant must only use prime divisibility, not exponent lifting.
Problem Understanding
A sequence $a_1,\ldots,a_k$ consists of distinct elements of ${1,\ldots,n}$ with $k\ge 2$, satisfying
$$n \mid a_i(a_{i+1}-1)$$
for $i=1,\ldots,k-1$. The goal is to prove that
$$n \nmid a_k(a_1-1).$$
The structure is cyclic except for the last edge, and the task is to show that closing the cycle is impossible under the given divisibility constraints.
The key difficulty is to understand how prime divisors of $n$ constrain transitions between consecutive terms.
Key Observations
Let $p$ be any prime dividing $n$, and let $p^e \parallel n$.
From
$$n \mid a_i(a_{i+1}-1),$$
it follows that $p \mid a_i(a_{i+1}-1)$. Therefore either $p \mid a_i$ or $p \mid (a_{i+1}-1)$.
This produces a strict logical dichotomy at the level of primes: if a prime $p$ is absent from $a_i$, then it must divide $a_{i+1}-1$, which in particular implies $p \nmid a_{i+1}$.
Thus the set of prime divisors of the terms cannot increase along the sequence.
This monotonicity of prime support is the central invariant.
Solution
Let $P$ be the set of primes dividing $n$. For each index $i$, define
$$S_i = {p \in P : p \mid a_i}.$$
We prove that $S_{i+1} \subseteq S_i$ for every $i$.
Fix a prime $p \in P$. If $p \notin S_i$, then $p \nmid a_i$. From
$$n \mid a_i(a_{i+1}-1),$$
we obtain $p \mid a_i(a_{i+1}-1)$, hence $p \mid (a_{i+1}-1)$. This implies $p \nmid a_{i+1}$, so $p \notin S_{i+1}$.
Thus every prime absent from $S_i$ is also absent from $S_{i+1}$, giving $S_{i+1} \subseteq S_i$.
Iterating,
$$S_1 \supseteq S_2 \supseteq \cdots \supseteq S_k.$$
Since $a_1,\ldots,a_k$ are distinct and lie in a finite cycle, we compare $S_k$ with $S_1$ using the same argument on the final assumption for contradiction.
Assume for contradiction that
$$n \mid a_k(a_1-1).$$
Applying the same reasoning to the pair $(a_k,a_1)$ yields
$$S_1 \subseteq S_k.$$
Hence $S_1 = S_2 = \cdots = S_k$; all terms have exactly the same set of prime divisors from $n$.
Now fix any prime power $p^e \parallel n$.
If $p \in S_1$, then $p \mid a_i$ for every $i$, so all $a_i$ are divisible by $p$.
If $p \notin S_1$, then $p \nmid a_i$ for every $i$. Then from
$$n \mid a_i(a_{i+1}-1),$$
we obtain $p \mid (a_{i+1}-1)$ for all $i$, hence every $a_i \equiv 1 \pmod p$. Because this holds for every $i$, the entire sequence lies in a single residue class modulo $p$.
Since this is true for every prime power $p^e \parallel n$, the Chinese Remainder Theorem forces all $a_i$ to be congruent modulo $n$. Indeed, for each prime $p^e \parallel n$, either all $a_i \equiv 0 \pmod p$ (if $p \in S_1$) or all $a_i \equiv 1 \pmod p$ (if $p \notin S_1$), and these conditions combine uniquely modulo $n$.
Therefore there exists a fixed residue $c \in {1,\ldots,n}$ such that
$$a_i \equiv c \pmod n$$
for all $i$. Since each $a_i$ already lies in ${1,\ldots,n}$, this implies $a_1=\cdots=a_k=c$, contradicting the assumption that the numbers are distinct and $k \ge 2$.
This contradiction shows that the assumption
$$n \mid a_k(a_1-1)$$
is impossible.
Therefore,
$$n \nmid a_k(a_1-1).$$
This completes the proof. ∎
Verification of Key Steps
The only nontrivial invariant used is the monotonicity of prime divisibility sets $S_{i+1} \subseteq S_i$. This follows directly from reducing the condition modulo each prime $p \mid n$, avoiding any unjustified lifting to prime powers.
The cycle closure step is handled by applying the same argument to the final pair, which forces equality of all $S_i$ and eliminates any possibility of drift in prime support.
The final contradiction uses the fact that fixing, for each prime power dividing $n$, whether all terms are divisible by the prime or all are congruent to $1$ modulo that prime forces a unique residue class modulo $n$, making distinctness impossible.
All cases for primes dividing $n$ are exhausted by splitting into $p \in S_1$ and $p \notin S_1$, which is exhaustive and stable under the derived inclusions.
Alternative Approaches
A graph-theoretic reformulation defines a directed graph on ${1,\ldots,n}$ with an edge $x \to y$ if $n \mid x(y-1)$. The argument above shows that any directed path forces a collapse of the vertex set into a single congruence class modulo $n$, implying the graph contains no directed cycle and no nontrivial directed path of distinct vertices.