1971 IMO Problems/Problem 3

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.

Solution

Wlog, assume $a_{n}\ge 3$ . Then say $p_{1}, p_{2}, \ldots, p_{k}\in \mathbb{N}$ are all the (pairwise distinct) primes dividing $2^{a_{n}}-3$ and let $a_{n+1}= a_{n}\cdot \prod_{i=1}^{k}(p_{i}-1)$ . Obviously $p_{i}$ is odd, for any $i \in \overline{1,k}$ . So $\prod_{i=1}^{k}p_{i}$ divides $2^{a_{n+1}}-1$ , by Fermat's little theorem, and $\gcd(2^{a_{n+1}}-3, 2^{a_{n}}-3) = 1$ . Now, by induction, it follows $\gcd(2^{a_{m}}-3, 2^{a_{n}}-3) = 1$ , for any distinct $m, n \in \mathbb{N}$ .

The above solution was posted and copyrighted by s.tringali. The original thread for this problem can be found here: [1]

1971 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1971 IMO Problems/Problem 3

Problem

Solution

See Also