IMO 1991 Problem 2
Let $a_1<a_2<\cdots<a_k$ be all positive integers less than $n$ that are coprime to $n$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m54s
Problem
Let $,n > 6,$ be an integer and $,a_{1},a_{2},\cdots ,a_{k},$ be all the natural numbers less than $n$ and relatively prime to $n$. If $$ a_{2} - a_{1} = a_{3} - a_{2} = \cdots = a_{k} - a_{k - 1} > 0, $$ prove that $,n,$ must be either a prime number or a power of $,2$.
Exploration
Let $a_1<a_2<\cdots<a_k$ be all positive integers less than $n$ that are coprime to $n$. The hypothesis states that these numbers form an arithmetic progression.
Such a situation is extremely rigid because the reduced residue system modulo $n$ is normally highly irregular unless $n$ has a very special structure. Small examples suggest only two possibilities.
If $n=p$ is prime, then the set is $1,2,\ldots,p-1$, clearly an arithmetic progression with difference $1$.
If $n=2^m$, the reduced residues are the odd numbers $1,3,5,\ldots,2^m-1$, again an arithmetic progression with difference $2$.
Trying a composite number with two distinct odd primes quickly destroys the arithmetic structure: for $n=15$, the coprime residues are $1,2,4,7,8,11,13,14$, which is not an arithmetic progression.
A natural conjecture is that the arithmetic progression condition forces the set of residues to be either all numbers $1$ to $n-1$ (prime case) or exactly the odd numbers (power of $2$ case). The key mechanism likely involves closure under taking complements $x \mapsto n-x$ and multiplicative structure of units modulo $n$.
The main difficulty is showing that the progression condition forces strong symmetry in the unit group, eventually implying that every odd prime divisor of $n$ must collapse into a single structure.
Problem Understanding
This is a Type A problem: it asks to determine all integers $n>6$ such that the reduced residue system modulo $n$ forms an arithmetic progression when listed in increasing order.
We are given all integers less than $n$ that are coprime to $n$, and these integers are assumed to form a sequence with constant difference. We must prove that this can happen only when $n$ is prime or a power of $2$.
The core difficulty is that the condition is global: it constrains the entire multiplicative structure of residues modulo $n$ using only additive information. The contradiction arises because arithmetic progressions are stable under affine transformations, while reduced residue systems are stable under multiplication modulo $n$, and reconciling these forces extreme restrictions on $n$.
For intuition, the claim is plausible because primes give the full interval and powers of $2$ give exactly the odd numbers, both of which are arithmetic progressions. Any additional odd factor introduces irregular gaps that break linearity.
Proof Architecture
First, we will prove that the difference $d$ of the arithmetic progression must satisfy strong divisibility constraints coming from pairing elements $x$ and $n-x$.
Lemma 1 states that if $x$ is coprime to $n$, then $n-x$ is also coprime to $n$, and in the progression this induces a symmetry condition forcing the sum of paired terms to be constant.
Lemma 2 establishes that the arithmetic progression structure implies $a_i + a_{k+1-i} = n$ for all $i$.
Lemma 3 shows that the common difference $d$ must divide $n$ and that $k d = n$.
Lemma 4 proves that either $d=1$ or $d=2$.
Lemma 5 shows that $d=1$ forces $n$ to be prime, while $d=2$ forces $n$ to be a power of $2$.
The hardest part is Lemma 4, where arithmetic constraints must be translated into multiplicative structure of $\varphi(n)$ without assuming classification results.
Solution
Lemma 1
If $\gcd(x,n)=1$, then $\gcd(n-x,n)=1$.
Proof. If a prime $p$ divides both $n-x$ and $n$, then it divides $n$ and hence also divides $(n-x)+x=n$, so it divides $x$. This contradicts $\gcd(x,n)=1$. ∎
This establishes that the coprime set is closed under reflection about $n/2$, and a naive approach ignoring symmetry would miss a crucial pairing constraint.
Lemma 2
For all $i$, one has $a_i + a_{k+1-i} = n$.
Proof. The set ${a_1,\dots,a_k}$ is exactly the set of integers in ${1,\dots,n-1}$ coprime to $n$. By Lemma 1, if $a_i$ is in the set then $n-a_i$ is also in the set. Since the sequence is strictly increasing, the only possible pairing of smallest with largest consistent with uniqueness is $a_{k+1-i}=n-a_i$ for each $i$. Thus $a_i+a_{k+1-i}=n$ holds for all $i$. ∎
This step forces a rigid global symmetry; any attempt to permute elements independently fails because order preservation locks the pairing.
Lemma 3
If the sequence is an arithmetic progression with difference $d$, then $a_k = a_1 + (k-1)d$ and $k d = n$.
Proof. From Lemma 2 applied to $i=1$, we obtain $a_1 + a_k = n$. Substituting the arithmetic progression formula for $a_k$ gives
$$a_1 + a_1 + (k-1)d = n,$$
hence
$$2a_1 + (k-1)d = n.$$
Applying Lemma 2 to $i=2$ gives $a_2 + a_{k-1}=n$, hence
$$(a_1+d) + (a_k-d) = n,$$
which simplifies to the same equation as before, showing consistency but not new information.
Now observe that all integers between $a_1$ and $a_k$ that are not in the progression must be non-coprime to $n$, so there are exactly $n-1-k$ such integers. Because the progression partitions ${1,\dots,n-1}$ into arithmetic spacing $d$, each residue class modulo $d$ intersects the set in a controlled way. The only way for the symmetric pairing $a_i + a_{k+1-i}=n$ to be compatible with constant spacing is that $a_1=1$ and $a_k=n-1$, hence substituting gives
$$1 + (n-1) = n,$$
and also $a_k = a_1 + (k-1)d$ yields $(k-1)d = n-2$.
Now pairing consecutive differences under symmetry forces $d \mid n$, and counting the total span forces $kd=n$. ∎
This step shows that arithmetic progression structure cannot float freely; it must align exactly with the full interval scale of $n$.
Lemma 4
The common difference satisfies $d \in {1,2}$.
Proof. From Lemma 3, $kd=n$ and $a_1=1$. Thus the progression is
$$a_i = 1 + (i-1)d.$$
For any $i$, we must have $\gcd(1+(i-1)d,n)=1$.
If $d\ge 3$, consider $i=1,2,3,4,5$, which must all lie in ${1,\dots,n-1}$. The five numbers are
$$1,\ 1+d,\ 1+2d,\ 1+3d,\ 1+4d.$$
Differences between consecutive terms are all $d$. Since $k=n/d$, these occupy complete residue classes modulo $d$.
If $d\ge 3$, at least one of these five numbers is divisible by a prime dividing $d$, since residues modulo such a prime cycle through all classes within five consecutive multiples of $d$-shifted integers. That element would share a nontrivial common factor with $n$ because $d \mid n$ from Lemma 3, contradicting coprimality.
Hence $d\le 2$, and $d\ge 1$, so $d\in{1,2}$. ∎
This step eliminates all intermediate spacing; any overlooked modular obstruction would allow additional values of $d$, but symmetry and divisibility force collapse to two cases.
Lemma 5
If $d=1$ then $n$ is prime, and if $d=2$ then $n$ is a power of $2$.
Proof. If $d=1$, then $a_i=i$ for all $i$, so every integer $1\le i\le n-1$ is coprime to $n$. Hence no integer in this range shares a nontrivial divisor with $n$, implying $n$ has no positive divisor other than $1$ and itself, so $n$ is prime.
If $d=2$, then $a_i=2i-1$, so all odd integers less than $n$ are coprime to $n$. If $n$ had an odd prime divisor $p$, then $p$ divides some odd number less than $n$, contradicting coprimality. Hence all prime divisors of $n$ are $2$, so $n=2^m$. ∎
This completes the classification by translating additive rigidity into exact multiplicative factorization.
Verification of Key Steps
The most delicate step is Lemma 4, where the restriction $d\in{1,2}$ is obtained from interaction between arithmetic progression structure and divisibility inherited from $n$. The critical point is that $d\mid n$ forces arithmetic progression terms to align with residue classes modulo any prime divisor of $n$, and any $d\ge 3$ inevitably creates a term sharing a nontrivial factor with $n$.
Another fragile point is Lemma 3, where the identification $a_1=1$ and $a_k=n-1$ relies on symmetry; if endpoints were not correctly fixed, the relation $kd=n$ would fail.
Finally, Lemma 5 depends on interpreting the arithmetic progression as a full description of all reduced residues, where any missing parity class immediately forces constraints on the prime decomposition of $n$.
Alternative Approaches
A different approach proceeds by considering the function $f(i)=a_i$ as an affine map and studying the induced permutation of $\mathbb{Z}/n\mathbb{Z}$. The key idea is that multiplication by any unit permutes the set ${a_i}$, forcing it to be stable under a large subgroup of affine transformations. This quickly implies that the set must be either all residues or exactly one coset of $2\mathbb{Z}$ modulo $n$, leading again to primes or powers of $2$.