Difference between revisions of "1991 IMO Problems/Problem 2"

Revision as of 05:13, 19 August 2025

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 ================

// Lemma 1: If $c$ is the number of numbers smaller than and coprime to a number $n$ where $n > 6$, then $c$ is even.\\ \text{Examples:} \\ n = 7: \text{numbers smaller than and coprime to 7 are } 1, 2, 3, 4, 5, 6 \Rightarrow c = 6 \text{ (even)}.\\ n = 8: \text{coprime numbers are } 1, 3, 5, 7 \Rightarrow c = 4 \text{ (even)}.\\ \text{Proof: If } q \text{ is coprime to } n, \text{ then } n-q \text{ is also coprime to } n.\\ \text{So for each } q < n/2, \text{ there exists } n-q > n/2 \text{ also coprime. Hence, } c \text{ is even.}\\ // Now, we consider the main problem: prove that coprime numbers are never in an arithmetic progression if $n > 6$ and $n$ is not prime or a power of two.\\ \text{Scenario 1: } n \text{ is odd} \\ \text{First two coprime numbers are } 1 \text{ and } 2.\\ \text{If in arithmetic progression, sequence would be } 1, 2, 3, \dots, n-1.\\ \text{But } n \text{ is only coprime to all numbers smaller than it if } n \text{ is prime.}\\ \text{Hence, odd } n \text{ coprime numbers form an arithmetic progression only if } n \text{ is prime.}\\ \text{Scenario 2: } n \text{ divisible by 4} \\ \text{Assume coprime numbers form an arithmetic progression: } 1, 1+d, 1+2d, \dots, 1+(c-1)d \\ \text{Sum: } S = c + \frac{c(c-1)d}{2} \\ \text{Also, by Lemma 1: sum must equal } \frac{c n}{2} \\ c + \frac{c(c-1)d}{2} = \frac{c n}{2} \Rightarrow 2 = n - d(c-1)\\ \text{Since } c-1 \text{ is odd and } n \text{ is even, } d \text{ must be even, gcd}(n,d) = 2.\\ \text{If } n \text{ divisible by 4, } d \text{ must divide 2, so } d = 2. \\ \text{Arithmetic progression } 1, 3, 5, \dots \text{ only possible if } n \text{ is a power of 2.}\\ \text{Scenario 3: } n \text{ not divisible by 4, but by 2 and an odd number} \\ n = 2f, f \text{ odd, } n > 6 \\ \text{Then } f-2 \text{ and } f+2 \text{ are consecutive coprime numbers to } n. \\ \text{Gap between them is 4, so gap between consecutive coprime numbers must be 4.}\\ \text{Numbers coprime to sequence } 1, 5, 9, 13, \dots \\ 6 \text{ is coprime to 1 and 5. For } n>6, \text{ must be coprime to 9 } \Rightarrow \text{coprime to 3, contradiction.}\\ \text{Hence, no } n>6 \text{ in this scenario satisfies the constraints.}\\ // Conclusion: For } n > 6, \text{ coprime numbers smaller than } n \text{ are never in an arithmetic progression unless } n \text{ is prime or a power of two.\\

@@ Line 66: / Line 66: @@
 This solution was posted and copyrighted by shinichiman. The original thread for this problem can be found here: [https://aops.com/community/p5878962]
-Solution 6
-\documentclass[12pt]{article}
+Solution 6 ================
-\usepackage{amsmath, amssymb}
-\begin{document}
+// Lemma 1: If \(c\) is the number of numbers smaller than and coprime to a number \(n\) where \(n > 6\), then \(c\) is even.\\ \text{Examples:} \\ n = 7: \text{numbers smaller than and coprime to 7 are } 1, 2, 3, 4, 5, 6 \Rightarrow c = 6 \text{ (even)}.\\ n = 8: \text{coprime numbers are } 1, 3, 5, 7 \Rightarrow c = 4 \text{ (even)}.\\ \text{Proof: If } q \text{ is coprime to } n, \text{ then } n-q \text{ is also coprime to } n.\\ \text{So for each } q < n/2, \text{ there exists } n-q > n/2 \text{ also coprime. Hence, } c \text{ is even.}\\ // Now, we consider the main problem: prove that coprime numbers are never in an arithmetic progression if \(n > 6\) and \(n\) is not prime or a power of two.\\ \text{Scenario 1: } n \text{ is odd} \\ \text{First two coprime numbers are } 1 \text{ and } 2.\\ \text{If in arithmetic progression, sequence would be } 1, 2, 3, \dots, n-1.\\ \text{But } n \text{ is only coprime to all numbers smaller than it if } n \text{ is prime.}\\ \text{Hence, odd } n \text{ coprime numbers form an arithmetic progression only if } n \text{ is prime.}\\ \text{Scenario 2: } n \text{ divisible by 4} \\ \text{Assume coprime numbers form an arithmetic progression: } 1, 1+d, 1+2d, \dots, 1+(c-1)d \\ \text{Sum: } S = c + \frac{c(c-1)d}{2} \\ \text{Also, by Lemma 1: sum must equal } \frac{c n}{2} \\ c + \frac{c(c-1)d}{2} = \frac{c n}{2} \Rightarrow 2 = n - d(c-1)\\ \text{Since } c-1 \text{ is odd and } n \text{ is even, } d \text{ must be even, gcd}(n,d) = 2.\\ \text{If } n \text{ divisible by 4, } d \text{ must divide 2, so } d = 2. \\ \text{Arithmetic progression } 1, 3, 5, \dots \text{ only possible if } n \text{ is a power of 2.}\\ \text{Scenario 3: } n \text{ not divisible by 4, but by 2 and an odd number} \\ n = 2f, f \text{ odd, } n > 6 \\ \text{Then } f-2 \text{ and } f+2 \text{ are consecutive coprime numbers to } n. \\ \text{Gap between them is 4, so gap between consecutive coprime numbers must be 4.}\\ \text{Numbers coprime to sequence } 1, 5, 9, 13, \dots \\ 6 \text{ is coprime to 1 and 5. For } n>6, \text{ must be coprime to 9 } \Rightarrow \text{coprime to 3, contradiction.}\\ \text{Hence, no } n>6 \text{ in this scenario satisfies the constraints.}\\ // Conclusion: For } n > 6, \text{ coprime numbers smaller than } n \text{ are never in an arithmetic progression unless } n \text{ is prime or a power of two.\\
-\section*{Solution}
-Let <math>c</math> be the number of positive integers smaller than and coprime to <math>n</math>, with <math>n>6</math>.
-\textbf{Lemma 1.} <math>c</math> is even.
-\textbf{Proof of Lemma 1.} If <math>q</math> is coprime to <math>n</math>, then so is <math>n-q</math>. Pairing <math>q</math> with <math>n-q</math> shows that <math>c</math> is even. \(\blacksquare\)
-Assume that the numbers smaller than <math>n</math> and coprime to <math>n</math> form an arithmetic progression with first term <math>1</math> and difference <math>d</math>:
-\[
-a_i = 1 + (i-1)d, \quad 1 \le i \le c.
-\]
-\textbf{Case 1: <math>n</math> is odd.}
-The first two coprime numbers are <math>1</math> and <math>2</math>. If they form an arithmetic progression, the sequence would continue <math>1,2,3,\dots,n-1</math>. This implies <math>n</math> is coprime to all numbers smaller than it, so <math>n</math> must be prime.
-\textbf{Case 2: <math>n</math> divisible by <math>4</math>.}
-Summing the arithmetic progression gives
-\[
-\sum_{i=1}^{c} a_i = c + \frac{c(c-1)}{2}d.
-\]
-By Lemma 1, pairing each <math>q</math> with <math>n-q</math> gives a total sum <math>c \cdot \frac{n}{2}</math>. Equating these,
-\[
-c + \frac{c(c-1)}{2}d = \frac{c n}{2} \implies 2 = n - d(c-1).
-\]
-Since <math>c-1</math> is odd and <math>n</math> is even, <math>d</math> must be even and <math>\gcd(n,d)=2</math>. Because <math>n</math> is divisible by <math>4</math>, the only possibility is <math>d=2</math>, which happens only if <math>n</math> is a power of two.
-\textbf{Case 3: <math>n</math> divisible by <math>2</math> but not by <math>4</math>.}
-Let <math>n=2f</math>, <math>f</math> odd. Then <math>f-2</math> and <math>f+2</math> are consecutive coprime numbers. The gap is <math>4</math>, so the progression is <math>1,5,9,13,\dots</math>. For <math>n>6</math>, the sequence eventually includes a multiple of <math>3</math>, contradicting coprimality.
-\textbf{Conclusion.} In all cases, the numbers smaller than <math>n</math> and coprime to <math>n</math> form an arithmetic progression only if <math>n</math> is prime or a power of <math>2</math>. \(\blacksquare\)
-\end{document}
 == See Also == {{IMO box|year=1991|num-b=1|num-a=3}}

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