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]

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]

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