1991 IMO Problems/Problem 2

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$ .

Solution 1

We use Bertrand's Postulate: for $u\ge 2$ is a positive integer, there is a prime in the interval $(u,2u)$ .

Clearly, $a_2$ must be equal to the smallest prime $p$ which does not divide $n$ . If $p=2$ , then $n$ is a prime since the common difference $a_{i+1}-a_i$ is equal to $1$ , i.e. all positive integers less than $n$ are coprime to $n$ . If, on the ther hand, $p=3$ , we find $n$ to be a power of $2$ : the positive integers less than $n$ and coprime to it are precisely the odd ones. We may thus assume that $p\ge 5$ . Furthermore, since $n>6$ , the positive integers less than $n$ and coprime to it cannot be $a_1,a_2$ alone, i.e. $k=\varphi(n)\ge 3$ .

By Bertrand's Postulate, the largest prime less than $p$ is strictly larger than $\frac{p-1}2$ , so it cannot divide $p-1$ . We will denote this prime by $q$ . We know that $q|n$ . It's easy to check that for $p\le 31$ there is a prime $r$ strictly between $a_2=p,\ a_3=2p-1$ . $rq|n$ , so, in particular, $pq<rq\le n$ . On the other hand, if $p>32$ , the two largest primes $r_1<r_2$ which are smaller than $q$ satisfy $r_2\ge\frac p4,\ r_1\ge\frac{r_2}2\ge\frac p8$ (again, Bertrand's Postulate), so $pq<\frac{p^2}{32}q\le r_1r_2q\le n$ so, once again, we have $pq<n$ (this is what I wanted to prove here).

Now, $q\not|p-1$ , and all the numbers $1,1+p-1,\ldots,1+(q-1)(p-1)$ are smaller than $n$ (they are smaller than $pq$ , which is smaller than $n$ , according to the paragraph above). One of these numbers, however, must be divisible by $q|n$ . Since our hypothesis tells us that all of them must be coprime to $n$ , we have a contradiction.

This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

Note

Bertrand actually allows for the bounds $(a,2a-2)$ for $a>3$ ; thus, since $a_2$ is the smallest prime not dividing $n$ , $a_3$ must equal $2a_2-1$ . Hence there cannot exist a prime in the bounds $(a_2,2a_2-1)$ , clearly untrue for $a_2>3$ by Bertrand. Then $a_2=2$ is clearly not possible, and $a_2=3$ does not work (unless $n$ is a power of $2$ ); hence the conclusion holds.

~eevee9406

Solution 2

Let $d=a_{i+1}-a_i$ . Then we have $a_i=1_1+d(i-1)=1+d(i-1)$ . Since $\gcd(n-1,n)=1$ , so $n-1$ is the largest positive integer smaller than $n$ and co-prime to $n$ . Thus, $a_k=n-1$ and $1+d(k-1)=n-1$ which shows $d(k-1)=n-2$ and so $d$ divides $n-2$ . We make two cases. Case 1: $n$ is odd. Then $\gcd(n-2,n)=1$ . So, every divisor of $n-2$ is co-prime to $n$ too, so is $d$ . Thus, there is a $j$ such that $d=a_j=1+d(j-1)$ which implies $d|1$ . Therefore, in this case, $d=1$ and we easily find that all numbers less than $n$ are co-prime to $n$ , so $n$ must be a prime. Case 2: $n$ is even. But then $\gcd(n-2,n)=2$ and also $d=1$ is ruled out. So $d>1$ . Say, $n=2l$ . Then, $d$ divides $2(l-1)$ . If $d$ is odd, $d|l$ and $d|l-1$ forcing $d|1$ , contradiction! So, $d=2s$ with $s|l-1$ . If $l=2r+1$ for some $r$ , then $\gcd(r,n)=1$ . So, again $r=1+d(j-1$ for a $j$ . If $s$ is odd, then $s|r$ and thus, $s|1$ . Similarly, we find that actually $d|2$ must occur. We finally have, $d=2$ . But then all odd numbers less than $n$ are co-prime to $n$ . So, $n$ does not have any odd factor i.e. $n=2^k$ for some $k\in\mathbb N$ .

This solution was posted and copyrighted by ngv. The original thread for this problem can be found here: [2]

Solution 3

We use Bonse's Inequality: $p_{m+1}^2 < p_1p_2\cdots p_m$ , for all $m \ge 4$ , $p_1 = 2$ .

Let $p$ denote the smallest prime which does not divide $n$ .

Case 1) $p = 2$ . This implies $n$ is a prime. Case 2) $p = 3$ . This implies $n = 2^k$ for some $k \in \mathbb{N}$ . Case 3) $p = 5$ . Since $n > 6$ , we have that $n > 9$ . Therefore $a_3 = 9$ , but $\gcd (n, 9) > 1$ . Case 4) $p \ge 7$ . Write $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ . We have $(p - 2)^2 < p_1p_2\cdots p_k \le n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ . Hence $(p-2)^2 = a_i$ , a contradiction since $\gcd(p-2, n) > 1$ .

This solution was posted and copyrighted by SFScoreLow. The original thread for this problem can be found here: [3]

Solution 4

Clearly, $a_1 = 1$ . Now let $p$ be the smallest prime number which is not a divisor of $n$ . Hence, $a_2 = p$ , and the common difference $d = p-1$ . Observe that since $a_k = n-1$ , we have that $d \mid a_k - a_1$ , or $p - 1 \mid a_k - a_1 = n-2$ . This means that all prime factors of $p-1$ are prime factors of $n-2$ . However, due to the minimality of $p$ , all primes factors of $p-1$ are prime factors of $n$ . By the Euclidean algorithm, the only prime factors of $p-1$ are $2$ , so $p = 2^{2^k} + 1$ or $p = 2$ , by the theory of Fermat primes. We will now do casework on $p$ .

Case 1: $p = 2$ This case is relatively easy. $a_2 = 2$ , so all numbers less than $n$ must be relatively prime to $n$ . However, if $n = pq$ , where $p > 1$ and $q > 1$ , observe that $p$ is not relatively prime to $n$ , so $n$ must be prime for this case to work.

Case 2: $k = 0$ and $p = 3$ . This case is somewhat tricky. Observe that $n$ is even. Since $a_2 = 3$ , we have that all numbers less than $n$ which are odd are relatively prime to $n$ . However, if $n$ has a odd divisor $p > 1$ , clearly $p$ is not relatively prime to $n$ , so $n$ must be a power of two.

Case 3: $k \ge 1$ . Note that $3$ must be a divisor of $n$ , so $a_k$ cannot be a multiple of $3$ for any $k$ . I will contradict this statement. First, I claim that $k = \phi(n) > 2$ for all integers $n > 6$ . $\phi{n} = 1$ is trivial, so let me show that $\phi(n) = 2$ has only solutions less than or equal to $6$ . Since $\phi$ is a multiplicative function, observe that $n$ cannot be a multiple of a prime greater than $3$ , because for such primes $p$ we have that $\phi(p^k) = (p-1)p^{k-1} \ge p-1 > 2$ , which is contradiction. Hence, $n$ is just composed of factors of $2$ and $3$ . If it divides both, and is of the form $2^m 3^n$ for $m$ and $n$ positive, we get that we need $2^{m} 3^{n-1} = 2$ , so $n = 1$ and $m = 1$ in this case. If it is of the form $n = 2^k$ , we get $k = 2$ . And if it is of the form $3^k$ , we get $k = 1$ . $3$ , $4$ , and $6$ are all less than or equal to $6$ , so $\phi(n) > 2$ . Now we're almost done. Since $k > 2$ , the number $a_3 = 2p-1$ must be in this sequence. However, $a_3 = 2p-1$ is of the form $2^{2^n+1} + 1$ , which is a multiple of $3$ , and we have contradiction, so we are done.

This solution was posted and copyrighted by va2010. The original thread for this problem can be found here: [4]

Solution 5

Clearly that $a_1=1$ . Let $a_{i+1}-a_i = d \; (1 \le i \le \varphi(n)-1)$ then $a_{i}=(i-1)d+1 \; \; (1 \le i \le \varphi(n)). \qquad (1)$ We can see that if $n$ is a prime then $n$ satisfies the condition. We consider the case when $n$ is a composite number. Let $p$ be the smallest prime divisor of $n$ then $p \le \sqrt{n}$ . Note that $\varphi (n) > \sqrt{n} \ge p$ for all prime $n>6$ since $p_i^{k_i}-p_i^{k_i-1} \ge p_i^{k_i/2}$ for all $p \ge 3$ . Therefore, if $p \nmid d$ then there will exists $1 \le i \le \varphi(n)$ such that $(i-1)d \equiv -1 \pmod{p}$ or $p \mid a_i$ , a contradiction since $\gcd (a_i,n)=1$ . Thus, $p \mid d$ . We consider two cases:

If $d \ge 2p$ then $p+1 \ne a_i \; (1 \le i \le \varphi(n))$ . Hence, $\gcd (p+1,n)>1$ . This means there exists a prime $q>p \ge 2$ such that $q \mid p+1$ . Since $q>p$ so we get $q=p+1$ or $p=2,q=3$ , a contradiction since $n>6$ . Thus, $d <2p$ or $d=p$ .

If $p=d=2$ then all odd numbers $a_i \le n$ are relatively prime to $n$ . This can only happen when $n=2^x \; (x \in \mathbb{N})$ .

If $p=d >3$ then $p+3 \ne a_i \; \forall 1 \le i \le \varphi(n)$ since $a_i \equiv 1 \pmod{p} \; \forall 1 \le i \le \varphi(n)$ . Thus, $\gcd (p+3,n)>1$ or there exist a prime $q>p>3$ such that $q \mid p+3$ . Note that $2 \mid p+3$ so $q \le \tfrac{p+3}{2}<p$ , a contradiction.

Thus, $n$ must be either a prime number or a power of $2$ . $\blacksquare$

This solution was posted and copyrighted by shinichiman. The original thread for this problem can be found here: [5]

Solution 6

\documentclass[12pt]{article} \usepackage{amsmath, amssymb}

\begin{document}

\section*{Proof}

We begin with a lemma:

\subsection*{Lemma 1} Let $c$ be the number of positive integers smaller than and coprime to $n$ , with $n > 6$ . Then $c$ is even.

\textbf{Example:} For $n = 7$ , the numbers smaller than and coprime to $7$ are $1,2,3,4,5,6$ , so $c=6$ , which is even. For $n = 8$ , the coprime numbers are $1,3,5,7$ , so $c=4$ , also even.

\textbf{Proof:} If $q$ is coprime to $n$ , then $n-q$ is also coprime to $n$ . For each $q < n/2$ that is coprime to $n$ , there exists $n-q > n/2$ also coprime to $n$ . Hence, $c$ is always even.

\bigskip

Now, we address the main question: prove that the numbers smaller than $n$ and coprime to $n$ never form an arithmetic progression if $n > 6$ and $n$ is neither prime nor a power of two. We consider three scenarios.

\subsection*{Scenario 1: $n$ is odd} The first two coprime numbers are $1$ and $2$ (since $n$ is odd). If the coprime numbers form an arithmetic progression, the sequence would continue as $1, 2, 3, 4, \dots, n-1$ . But this implies that $n$ is coprime to all numbers smaller than it, which is only true if $n$ is prime. \textbf{Conclusion:} For odd $n$ , the numbers coprime to $n$ cannot form an arithmetic progression unless $n$ is prime.

\subsection*{Scenario 2: $n$ divisible by $4$ } Assume the coprime numbers form an arithmetic progression: \[ 1, 1+d, 1+2d, \dots, 1+(c-1)d, \] where $c$ is the number of coprime numbers. The sum of this progression is: \[ \sum = c + \frac{c(c-1)}{2}d. \] By Lemma 1, pairing each $q$ with $n-q$ yields a total sum of $c \cdot \frac{n}{2}$ . Equating the two sums: \[ c + \frac{c(c-1)}{2}d = \frac{c n}{2} \implies 2 = n - d(c-1). \] Since $c-1$ is odd (Lemma 1) and $n$ is even, $d$ must be even. Also, $\gcd(n,d)=2$ . Because $n$ is divisible by $4$ , $d$ can only be $2$ , giving an arithmetic progression with difference $2$ . This only occurs if $n$ is a power of two.

\subsection*{Scenario 3: $n$ divisible by $2$ but not by $4$ } Let $n = 2f$ , where $f$ is odd and $n>6$ . The numbers $f-2$ and $f+2$ are coprime to $2f$ . But $f-1$ , $f$ , and $f+1$ are not coprime. Hence, consecutive coprime numbers have a gap of $4$ , forming a progression like $1,5,9,13,\dots$ . However, for $n>6$ , this sequence eventually includes a multiple of $3$ , breaking the progression.

\bigskip

\textbf{Conclusion:} In all three scenarios, the numbers smaller than $n$ and coprime to $n$ do not form an arithmetic progression unless $n$ is prime or a power of two. \qed

\end{document}

1991 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search