IMO 1971 · Problem 3

Prove that the set of integers of the form \(2^k-3\) \((k=2,3,\ldots)\) contains an infinite subset in which every two members are relatively prime.

Official text of the problem. Official problem paper (PDF)

Solution

We construct strictly increasing exponents \(k_1,k_2,\ldots\) such that the numbers \(2^{k_i}-3\) are pairwise relatively prime.

Start with \(k_1=3\), giving \(2^{k_1}-3=5\). Suppose that \(k_1<\cdots<k_r\) have already been chosen with the required property, and put \[ M=\prod_{i=1}^{r}(2^{k_i}-3). \] Every factor is odd, so \(M\) is odd.

Among the \(M+1\) integers \[ 2^0,2^1,\ldots,2^M, \] two have the same remainder modulo \(M\). Thus, for some \(0\le u<v\le M\), \[ 2^u\equiv2^v\pmod M. \] Since \(M\) is odd, \(2^u\) is relatively prime to \(M\), so cancellation gives \[ 2^d\equiv1\pmod M,\qquad d=v-u\ge1. \]

Now set \[ k_{r+1}=2+k_r d. \] Then \(k_{r+1}>k_r\), and \[ 2^{k_{r+1}}-3 =4(2^d)^{k_r}-3 \equiv4-3=1\pmod M. \] Consequently, \(2^{k_{r+1}}-3\) is relatively prime to \(M\), and hence to each previously chosen number \(2^{k_i}-3\).

The construction therefore continues indefinitely. Because the exponents strictly increase, the resulting numbers are distinct, so \[ \{2^{k_i}-3:i=1,2,\ldots\} \] is the required infinite subset.

The solution was checked against John Scholes' IMO solution archive (Kalva).