IMO 1971 Problem 3
The sequence begins
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 3m43s
Problem
Prove that the set of integers of the form $2^k - 3 (k = 2, 3, \cdots)$ contains an infinite subset in which every two members are relatively prime.
Exploration
The sequence begins
$$2^2-3=1,\qquad 2^3-3=5,\qquad 2^4-3=13,\qquad 2^5-3=29,$$
$$2^6-3=61,\qquad 2^7-3=125,\qquad 2^8-3=253.$$
Among these numbers,
$$\gcd(125,5)=5,\qquad \gcd(253,11)=11,$$
since
$$2^7-3=5^3,\qquad 2^8-3=11\cdot 23.$$
Thus the whole sequence is far from pairwise relatively prime.
The problem asks only for an infinite subset with pairwise coprime elements. A natural idea is to construct the subset inductively. Suppose we already selected finitely many terms
$$2^{n_1}-3,\dots,2^{n_r}-3.$$
If a prime $p$ divides both $2^m-3$ and $2^n-3$, then
$$2^m\equiv 2^n\equiv 3 \pmod p,$$
hence
$$2^{m-n}\equiv 1 \pmod p.$$
So the exponents that produce divisibility by a fixed prime lie in a single residue class modulo the order of $2$ modulo $p$. This suggests that for each previously chosen prime divisor, only certain congruence classes of exponents are forbidden.
A stronger and more useful statement emerges from the standard identity
$$\gcd(2^m-3,2^n-3)\mid 2^{m-n}-1.$$
Indeed, if a number divides both $2^m-3$ and $2^n-3$, then it divides their difference
$$2^m-2^n=2^n(2^{m-n}-1).$$
Since any common divisor of $2^m-3$ and $2^n-3$ is odd, it is relatively prime to $2^n$, hence it divides $2^{m-n}-1$.
The key difficulty is to guarantee infinitely many choices. If finitely many congruence classes are forbidden modulo finitely many integers, the Chinese remainder theorem should allow infinitely many permissible exponents.
A more concrete strategy appears. Assume we have already chosen exponents
$$n_1<n_2<\cdots<n_r.$$
Let
$$a_i=2^{n_i}-3.$$
Every prime divisor $p$ of any $a_i$ imposes a forbidden congruence class on future exponents $n$, namely the class for which
$$2^n\equiv 3\pmod p.$$
Since $2^{n_i}\equiv 3\pmod p$, this means
$$n\equiv n_i \pmod{\operatorname{ord}_p(2)}.$$
Avoiding all these finitely many classes ensures coprimality with every previous element.
The most delicate point is proving rigorously that avoiding those congruence classes indeed forces the gcd to be $1$, because one must rule out every common prime divisor simultaneously.
Problem Understanding
We consider the integers
$$2^k-3,\qquad k=2,3,4,\dots.$$
The task is to prove that among these integers there exists an infinite collection such that every two distinct members of the collection are relatively prime.
This is a Type B problem. The statement already specifies what must be proved, namely the existence of an infinite pairwise coprime subset.
The mathematical objects involved are integers of exponential form and their prime divisors. The central issue is that the sequence itself is not pairwise coprime. For example,
$$2^3-3=5,\qquad 2^7-3=125,$$
so repeated prime factors occur. A naive attempt to take all terms fails immediately.
The core difficulty is controlling all common divisors simultaneously. Whenever a prime $p$ divides some term $2^m-3$, infinitely many other exponents can produce numbers divisible by $p$. One must show that despite these recurring divisibility patterns, infinitely many exponents remain available.
The decisive insight is that for a fixed prime $p$, the exponents $n$ satisfying
$$p\mid 2^n-3$$
form a single congruence class modulo the multiplicative order of $2$ modulo $p$. Since only finitely many primes are involved at each stage of an inductive construction, only finitely many congruence classes must be avoided.
Proof Architecture
The proof proceeds inductively.
First, we establish a divisibility lemma. If a prime $p$ divides both $2^m-3$ and $2^n-3$, then
$$2^{m-n}\equiv 1\pmod p.$$
This follows by subtracting the two congruences and using that $p\neq 2$.
Second, for a fixed prime $p$ dividing some chosen term $2^{n_i}-3$, we characterize all exponents $n$ for which $p\mid 2^n-3$. They are exactly those satisfying
$$n\equiv n_i \pmod{d_p},$$
where $d_p$ is the multiplicative order of $2$ modulo $p$.
Third, we perform the inductive construction. Suppose finitely many exponents
$$n_1<n_2<\cdots<n_r$$
have already been chosen so that the corresponding numbers are pairwise relatively prime. Let $S$ be the finite set of all prime divisors of the selected numbers. For each $p\in S$, one residue class modulo $d_p$ must be avoided. Since a modulus $d_p$ has $d_p-1$ remaining classes, we can choose an exponent $n$ simultaneously avoiding all forbidden classes by the Chinese remainder theorem.
Finally, we prove that the new number $2^n-3$ is relatively prime to every previous chosen number, which completes the induction.
The step most likely to fail under insufficient scrutiny is the transition from congruence avoidance to pairwise coprimality. One must prove that every possible common prime divisor is excluded, not merely the previously visible ones.
Solution
Define
$$a_k=2^k-3,\qquad k\ge 2.$$
We shall construct inductively an infinite sequence of indices
$$n_1<n_2<n_3<\cdots$$
such that the integers
$$a_{n_1},a_{n_2},a_{n_3},\dots$$
are pairwise relatively prime.
We begin with several explicit cases:
$$a_2=1,\qquad a_3=5,\qquad a_4=13,\qquad a_5=29,\qquad a_6=61.$$
The numbers
$$5,13,29,61$$
are pairwise relatively prime. Thus the desired property is at least plausible for initial values.
Lemma 1
Let $m>n\ge 2$, and let $p$ be a prime satisfying
$$p\mid (2^m-3),\qquad p\mid (2^n-3).$$
Then
$$2^{m-n}\equiv 1\pmod p.$$
Proof
From
$$2^m\equiv 3\pmod p,\qquad 2^n\equiv 3\pmod p,$$
we obtain
$$2^m-2^n\equiv 0\pmod p.$$
Hence
$$2^n(2^{m-n}-1)\equiv 0\pmod p.$$
Since
$$2^n\equiv 3\pmod p,$$
the prime $p$ cannot equal $2$. Therefore $2^n$ is invertible modulo $p$. Multiplying by its inverse yields
$$2^{m-n}-1\equiv 0\pmod p.$$
Thus
$$2^{m-n}\equiv 1\pmod p.$$
∎
This lemma establishes that every common prime divisor forces a congruence relation between the exponents, and without extracting this relation the later avoidance argument would have no foundation.
Lemma 2
Fix an integer $r\ge 2$, and let $p$ be a prime divisor of $a_r=2^r-3$. Let $d_p$ denote the multiplicative order of $2$ modulo $p$. Then for every integer $n\ge 2$,
$$p\mid (2^n-3)$$
if and only if
$$n\equiv r\pmod{d_p}.$$
Proof
Since $p\mid (2^r-3)$,
$$2^r\equiv 3\pmod p.$$
Assume first that
$$p\mid (2^n-3).$$
Then
$$2^n\equiv 3\pmod p.$$
Combining this with
$$2^r\equiv 3\pmod p$$
gives
$$2^n\equiv 2^r\pmod p.$$
Hence
$$2^{n-r}\equiv 1\pmod p.$$
By definition of the order $d_p$, this implies
$$d_p\mid (n-r),$$
so
$$n\equiv r\pmod{d_p}.$$
Conversely, assume
$$n\equiv r\pmod{d_p}.$$
Then
$$n-r=d_p t$$
for some integer $t$. Since $2^{d_p}\equiv 1\pmod p$,
$$2^n=2^r(2^{d_p})^t\equiv 2^r\pmod p.$$
Because
$$2^r\equiv 3\pmod p,$$
we obtain
$$2^n\equiv 3\pmod p,$$
hence
$$p\mid (2^n-3).$$
∎
This lemma identifies precisely which exponents produce divisibility by a fixed prime, and any weaker statement would leave open the possibility of hidden common divisors.
We now perform the inductive construction.
Choose
$$n_1=3,$$
so
$$a_{n_1}=5.$$
Assume that for some $t\ge 1$ we have already chosen integers
$$n_1<n_2<\cdots<n_t$$
such that
$$a_{n_1},a_{n_2},\dots,a_{n_t}$$
are pairwise relatively prime.
Let $S$ be the finite set of all prime divisors of the product
$$a_{n_1}a_{n_2}\cdots a_{n_t}.$$
For each prime $p\in S$, there exists a unique index $i(p)$ such that
$$p\mid a_{n_{i(p)}}.$$
Indeed, pairwise coprimality guarantees that a prime divisor cannot divide two distinct chosen terms.
Let $d_p$ denote the multiplicative order of $2$ modulo $p$. By Lemma 2,
$$p\mid (2^n-3)$$
holds exactly for exponents satisfying
$$n\equiv n_{i(p)}\pmod{d_p}.$$
For every $p\in S$, select a residue class
$$c_p \pmod{d_p}$$
such that
$$c_p\not\equiv n_{i(p)}\pmod{d_p}.$$
This is possible because $d_p\ge 2$, as $2\not\equiv 1\pmod p$.
By the Chinese remainder theorem, the simultaneous congruences
$$n\equiv c_p\pmod{d_p}\qquad (p\in S)$$
have infinitely many integer solutions. Choose one such solution $n$ satisfying
$$n>n_t.$$
Define
$$n_{t+1}=n.$$
We claim that
$$a_{n_{t+1}}$$
is relatively prime to every previous chosen term.
Suppose, toward a contradiction, that for some $j\le t$,
$$\gcd(a_{n_{t+1}},a_{n_j})>1.$$
Then some prime $p$ satisfies
$$p\mid a_{n_{t+1}},\qquad p\mid a_{n_j}.$$
Since every prime divisor of $a_{n_j}$ belongs to $S$, the prime $p$ lies in $S$. By Lemma 2,
$$n_{t+1}\equiv n_j\pmod{d_p}.$$
But $j=i(p)$, because $p$ divides exactly one previously chosen term. Hence
$$n_{t+1}\equiv n_{i(p)}\pmod{d_p}.$$
This contradicts the defining congruence
$$n_{t+1}\equiv c_p\pmod{d_p},$$
where
$$c_p\not\equiv n_{i(p)}\pmod{d_p}.$$
Thus
$$\gcd(a_{n_{t+1}},a_{n_j})=1$$
for every $j\le t$. Consequently,
$$a_{n_1},a_{n_2},\dots,a_{n_t},a_{n_{t+1}}$$
are pairwise relatively prime.
By induction, there exists an infinite subset of the set
$${2^k-3:k\ge 2}$$
whose elements are pairwise relatively prime.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the derivation
$$2^{m-n}\equiv 1\pmod p$$
from the assumptions
$$p\mid (2^m-3),\qquad p\mid (2^n-3).$$
Starting again from scratch,
$$2^m\equiv 3\pmod p,\qquad 2^n\equiv 3\pmod p.$$
Subtracting gives
$$2^m-2^n\equiv 0\pmod p.$$
Factoring,
$$2^n(2^{m-n}-1)\equiv 0\pmod p.$$
A careless argument might divide by $2^n$ without checking invertibility modulo $p$. The justification is that $p\neq 2$, because $2^n-3$ is odd. Hence $2^n$ has a multiplicative inverse modulo $p$, and the division is legitimate.
The second delicate point is the use of the Chinese remainder theorem. The moduli $d_p$ need not be pairwise coprime. The standard form of the theorem for arbitrary moduli requires compatibility conditions. Here compatibility is automatic because for each modulus only one congruence condition is imposed. One may also avoid this issue entirely by choosing the congruences inductively. Suppose congruences have already been imposed modulo
$$d_{p_1},\dots,d_{p_r}.$$
The current solution set is an arithmetic progression. Since only one residue class modulo $d_{p_{r+1}}$ is forbidden, infinitely many terms of the progression avoid it. Thus the construction proceeds without requiring coprime moduli.
The third delicate point is proving that every common prime divisor is excluded. A superficial argument might only exclude the primes already used once in the construction. The actual proof must show that any prime dividing both a new term and an old term belongs to $S$, then invoke Lemma 2 to force the forbidden congruence. Without the uniqueness statement for $i(p)$, the contradiction would not follow.
Alternative Approaches
A different proof begins with the identity
$$\gcd(2^m-3,2^n-3)\mid 2^{m-n}-1.$$
One can then choose exponents recursively so that every difference
$$n_i-n_j$$
avoids all divisors arising from previously selected common factors. The construction becomes a problem about avoiding finitely many arithmetic progressions. This approach is shorter formally, but it obscures the exact mechanism governing repeated prime divisibility.
Another method uses primitive prime divisors. Results of Bang and Zsigmondy imply that for almost every exponent $n$, the number $2^n-3$ possesses a prime divisor not appearing in earlier terms. One could then select terms recursively using these new primes. That route depends on a powerful theorem far deeper than the problem requires, whereas the congruence argument above relies only on elementary modular arithmetic and the Chinese remainder theorem.