Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1991 IMO Problems/Problem 2"
Line 73: Line 73:
 
\begin{document}
 
\begin{document}
  
−
\section*{Proof}
+
\section*{Solution}
  
−
We begin with a lemma:
+
Let <math>c</math> be the number of positive integers smaller than and coprime to <math>n</math>, with <math>n>6</math>. 
  
−
\subsection*{Lemma 1}
+
\textbf{Lemma 1.} <math>c</math> is even.   
−
Let <math>c</math> be the number of positive integers smaller than and coprime to <math>n</math>, with <math>n > 6</math>. Then <math>c</math> is even.   
 
  
−
\textbf{Example:}
+
\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\)
−
For <math>n = 7</math>, the numbers smaller than and coprime to <math>7</math> are <math>1,2,3,4,5,6</math>, so <math>c=6</math>, which is even.
 
−
For <math>n = 8</math>, the coprime numbers are <math>1,3,5,7</math>, so <math>c=4</math>, also even.
 
  
−
\textbf{Proof:} 
+
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>:
−
If <math>q</math> is coprime to <math>n</math>, then <math>n-q</math> is also coprime to <math>n</math>. For each <math>q < n/2</math> that is coprime to <math>n</math>, there exists <math>n-q > n/2</math> also coprime to <math>n</math>. Hence, <math>c</math> is always even. 
+
\[
−
 
+
a_i = 1 + (i-1)d, \quad 1 \le i \le c.
−
\bigskip
+
\]
−
 
 
−
Now, we address the main question: prove that the numbers smaller than <math>n</math> and coprime to <math>n</math> never form an arithmetic progression if <math>n > 6</math> and <math>n</math> is neither prime nor a power of two. We consider three scenarios.
 
  
−
\subsection*{Scenario 1: <math>n</math> is odd}
+
\textbf{Case 1: <math>n</math> is odd.}
−
The first two coprime numbers are <math>1</math> and <math>2</math> (since <math>n</math> is odd). If the coprime numbers form an arithmetic progression, the sequence would continue as <math>1, 2, 3, 4, \dots, n-1</math>. But this implies that <math>n</math> is coprime to all numbers smaller than it, which is only true if <math>n</math> is prime.   
+
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{Conclusion:} For odd <math>n</math>, the numbers coprime to <math>n</math> cannot form an arithmetic progression unless <math>n</math> is prime.
 
  
−
\subsection*{Scenario 2: <math>n</math> divisible by <math>4</math>}
+
\textbf{Case 2: <math>n</math> divisible by <math>4</math>.}
−
Assume the coprime numbers form an arithmetic progression: 
+
Summing the arithmetic progression gives
 
\[
 
\[
−
1, 1+d, 1+2d, \dots, 1+(c-1)d,
+
\sum_{i=1}^{c} a_i = c + \frac{c(c-1)}{2}d.
 
\]   
 
\]   
−
where <math>c</math> is the number of coprime numbers. The sum of this progression is: 
+
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,
−
\[
 
−
\sum = c + \frac{c(c-1)}{2}d.
 
−
\] 
 
−
By Lemma 1, pairing each <math>q</math> with <math>n-q</math> yields a total sum of <math>c \cdot \frac{n}{2}</math>. Equating the two sums: 
 
 
\[
 
\[
 
c + \frac{c(c-1)}{2}d = \frac{c n}{2} \implies 2 = n - d(c-1).
 
c + \frac{c(c-1)}{2}d = \frac{c n}{2} \implies 2 = n - d(c-1).
 
\]   
 
\]   
−
Since <math>c-1</math> is odd (Lemma 1) and <math>n</math> is even, <math>d</math> must be even. Also, <math>\gcd(n,d)=2</math>. Because <math>n</math> is divisible by <math>4</math>, <math>d</math> can only be <math>2</math>, giving an arithmetic progression with difference <math>2</math>. This only occurs if <math>n</math> is a power of two.
+
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.
  
−
\subsection*{Scenario 3: <math>n</math> divisible by <math>2</math> but not by <math>4</math>}
+
\textbf{Case 3: <math>n</math> divisible by <math>2</math> but not by <math>4</math>.}
−
Let <math>n = 2f</math>, where <math>f</math> is odd and <math>n>6</math>. The numbers <math>f-2</math> and <math>f+2</math> are coprime to <math>2f</math>. But <math>f-1</math>, <math>f</math>, and <math>f+1</math> are not coprime. Hence, consecutive coprime numbers have a gap of <math>4</math>, forming a progression like <math>1,5,9,13,\dots</math>. However, for <math>n>6</math>, this sequence eventually includes a multiple of <math>3</math>, breaking the progression.   
+
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.   
  
−
\bigskip
+
\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\)
  
−
\textbf{Conclusion:} In all three scenarios, the numbers smaller than <math>n</math> and coprime to <math>n</math> do not form an arithmetic progression unless <math>n</math> is prime or a power of two. 
+
\end{document}
−
\qed
 
  
−
\end{document}
 
  
  
 
== See Also == {{IMO box|year=1991|num-b=1|num-a=3}}
 
== See Also == {{IMO box|year=1991|num-b=1|num-a=3}}

Revision as of 05:11, 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

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

\begin{document}

\section*{Solution}

Let $c$ be the number of positive integers smaller than and coprime to $n$, with $n>6$.

\textbf{Lemma 1.} $c$ is even.

\textbf{Proof of Lemma 1.} If $q$ is coprime to $n$, then so is $n-q$. Pairing $q$ with $n-q$ shows that $c$ is even. \(\blacksquare\)

Assume that the numbers smaller than $n$ and coprime to $n$ form an arithmetic progression with first term $1$ and difference $d$: \[ a_i = 1 + (i-1)d, \quad 1 \le i \le c. \]

\textbf{Case 1: $n$ is odd.} The first two coprime numbers are $1$ and $2$. If they form an arithmetic progression, the sequence would continue $1,2,3,\dots,n-1$. This implies $n$ is coprime to all numbers smaller than it, so $n$ must be prime.

\textbf{Case 2: $n$ divisible by $4$.} Summing the arithmetic progression gives \[ \sum_{i=1}^{c} a_i = c + \frac{c(c-1)}{2}d. \] By Lemma 1, pairing each $q$ with $n-q$ gives a total sum $c \cdot \frac{n}{2}$. Equating these, \[ c + \frac{c(c-1)}{2}d = \frac{c n}{2} \implies 2 = n - d(c-1). \] Since $c-1$ is odd and $n$ is even, $d$ must be even and $\gcd(n,d)=2$. Because $n$ is divisible by $4$, the only possibility is $d=2$, which happens only if $n$ is a power of two.

\textbf{Case 3: $n$ divisible by $2$ but not by $4$.} Let $n=2f$, $f$ odd. Then $f-2$ and $f+2$ are consecutive coprime numbers. The gap is $4$, so the progression is $1,5,9,13,\dots$. For $n>6$, the sequence eventually includes a multiple of $3$, contradicting coprimality.

\textbf{Conclusion.} In all cases, the numbers smaller than $n$ and coprime to $n$ form an arithmetic progression only if $n$ is prime or a power of $2$. \(\blacksquare\)

\end{document}


See Also

1991 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_IMO_Problems/Problem_2&oldid=258307"