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

We begin firstly by showing that if $c$ be the number of numbers smaller than and coprime to a number $n$ , such that $n > 2$ , then $c$ is even. This is very easily visible; if $q$ is coprime to $n$ , then $n-q$ is also coprime to $n$ . We see that all the coprime numbers are kind of symmetric around $\frac{n}{2}$ , and for $n > 2$ , $\frac{n}{2}$ is never coprime with $n$ , and it is easy to see that $c$ is always even for $n > 2$ .

This question essentially asks us that for $n > 6$ , the numbers smaller than and coprime to n never form an arithmetic progression unless n is a power of two or n is prime.

Now, we break this question into three scenarios:

Scenario 1: $n$ is odd. If a number is odd, then it is coprime with $2$ . All numbers are coprime with $1$ . So, the numbers smaller than and coprime to $n$ begin with 1, 2, .. If this is truly an arithemtic sequence up to $n$ , then that means that $n$ is coprime to all number smaller than itself. But, if $n$ is not prime, then it has a prime factor smaller than itself, and the arithmetic sequence would break, as that prime factor won't be included in the coprime numbers. So, if $n$ is odd, and the numbers smaller than and coprime to $n$ form an arithemtic sequence, then $n$ is a prime.

Scenario 2: $n$ is divisible by $4$ . It seems like we have nothing to argue here. So, we do something else here; we assume that the numbers smaller than $n$ form an arithemtic sequence like $1$ , $1+d$ , ... , $1+(c-1)d$ (where $c$ is the number of numbers smaller than and coprime to $n$ ), and sum them. The sum is $c + \frac{c(c-1)(d)}{2}$ . If you remember the part where we proved that all these numbers are symmetric around $\frac{n}{2}$ , we can see that we can sum these numbers another way, and find their sum to be $\frac{c(n)}{2}$ . So, $c + \frac{c(c-1)(d)}{2}$ = $\frac{c(n)}{2}$ , which means $2 = n - d(c-1)$ . $n$ here is even, $c-1$ is odd, so $d$ must be even too, otherwise the LHS will not be even. Also, gcd( $n$ , $d$ ) = $2$ , and as $n$ is divisible by $4$ , it means that $d$ is only divisible by $2$ , and not $4$ , because then gcd( $n$ , $d$ ) = $4$ , and the LHS would be a multiple of $4$ , which it is not. Before going on further, we'll see another very important thing, that $d$ is made up of prime factors that all divide $n$ , the proof of which is very trivial. But, if there is another prime which divides $n$ and $d$ , then that would mean that gcd( $n$ , $d$ ) != 2, which is false, thus $d$ must be divisible by $2$ , and not $4$ or any other prime number, which just means $d = 2$ . So, Our arithmmetic progression is like $1$ , $3$ , $5$ , .. , $n-1$ , implying that $n$ is coprime to all the odd numbers smaller than it. But, if $n$ has some odd prime factors, then that would mean that that odd prime is not coprime to $n$ , a contradiction, so, $n$ is only made up of powers of $2$ , that is, $n$ is a power of two greater than or equal to $4$ . The problem with $4$ is that it is only coprime to two numbers smaller than itself, which obviously form an arithemtic progression. But, as $n > 6$ here, we are on the safe side.

Scenario 3: $n$ is divisible by $2$ , but not $4$ . Let $n$ = $2x$ , where $x$ is odd. Before making anymore arguments, we see that $x-2$ and $x+2$ are consecutive coprime numbers to $2x$ . So, the arithemtic progression must have difference $4$ . Our number $n$ must be coprime to some prefix of the sequence $1$ , $5$ , $9$ , ..., and only that prefix. The moment $n > 6$ , $n$ must be coprime to $9$ (it's easy to see why), and thus also coprime to $3$ , which breaks this progression. Thus, for $n > 6$ , we can see that no number of the form $2x$ satisfies the conditions of the problem. The proof is done Courtesy of EobardThawne

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