IMO 1991 · Problem 2

Let \(n>6\) be an integer and \(a_1,a_2,\ldots,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\).

Official text of the problem. Official problem paper (PDF)

Solution

Let \(d\) be the common difference. Since the terms are increasing and include every natural number less than \(n\) and relatively prime to \(n\), we have \[ a_1=1,\qquad a_k=n-1,\qquad a_i=1+(i-1)d. \] In particular, the difference of any two numbers in the list is divisible by \(d\).

If \(n\) is odd, both \(1\) and \(2\) are relatively prime to \(n\). Thus \(d\mid 1\), so \(d=1\). Consequently every integer from \(1\) to \(n-1\) is relatively prime to \(n\). A composite \(n\) would have a divisor strictly between \(1\) and \(n\), contradicting this. Hence \(n\) is prime.

Now suppose that \(n\) is even. Every term in the list is odd, so \(d\) is even. We show that \(d=2\). Write \(n=2m\).

  • If \(m\) is even, the numbers \(m-1\) and \(m+1\) lie between \(1\) and \(n-1\), and \[ \gcd(2m,m-1)=\gcd(2,m-1)=1,\qquad \gcd(2m,m+1)=\gcd(2,m+1)=1. \] Thus both occur in the list. Their difference is \(2\), so \(d\mid 2\).

  • If \(m\) is odd, the hypothesis \(n>6\) gives \(m\ge5\). Hence \(m-4\) and \(m-2\) are positive odd integers less than \(n\). Moreover, \[ \gcd(2m,m-4)=\gcd(8,m-4)=1,\qquad \gcd(2m,m-2)=\gcd(4,m-2)=1. \] These two numbers also occur in the list and differ by \(2\), so again \(d\mid 2\).

Since \(d\) is positive and even, in either case \(d=2\). The list therefore consists of all odd integers from \(1\) to \(n-1\).

If \(n\) had an odd prime divisor \(p\), then, because \(n\) is even, \(1<p<n\). Thus \(p\) would belong to the list, contradicting \(\gcd(p,n)=p>1\). Consequently \(2\) is the only prime divisor of \(n\), and \(n\) is a power of \(2\).

This proves the required conclusion. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).