1971 IMO Problems/Problem 3

Revision as of 13:58, 29 January 2021 by Hamstpan38825 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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]

See Also

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