Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1971 IMO Problems/Problem 3

Revision as of 17:03, 21 December 2024 by Pf02 (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]


Remarks (added by pf02, December 2024)

1. The solution above is incomplete, and somewhat misleading, to such an extent that it can not be called a "Solution". The problem is with the statement "by induction, it follows $\gcd(2^{a_m} - 3, 2^{a_n} - 3) = 1$, for any distinct $m, n \in \mathbb{N}$". This statement is not clear at all, it needs a proof. But, as we will see below, we don't need to do this step at all.

2. Below, I will re-phrase the solution, and complete it.


Solution revised and completed

Denote $A_n = 2^{a_n} - 3$. The plan is to construct recursively a sequence $a_1 < a_2 < \dots < a_n < \dots$ such that $A_n$ and $A_k$ are relatively prime for all $k < n$.

Let $a_1 = 3$. (Note that any other number $> 3$ would serve just as well.)

Let $p_{1,1}, \dots, p_{1,k_1}$ be all the prime factors of $A_1 = 2^{a_1} - 3$. (Note that we did not specify whether any prime factors are repeated or not. It does not matter for the proof, the important thing is to take all prime factors.) In our case, $k_1 = 1$ and $p_{1,1} = 5$ since we took $a_1 = 3$.

Define $a_2 = a_1 (p_{1,1} - 1) \dots (p_{1,k_1} - 1)$. In our case $a_2 = 3 (5 - 1) = 12$.

Define $\{a_n\}$ recursively: let $\{p_{(n-1),1}, \dots, p_{(n-1),k_{n-1}}\}$ be all the prime factors of $A_{n-1} = 2^{a_{n-1}} - 3$. (Note again that we don't care whether factors are repeated or not.) Let us take $a_n = a_{n-1} (p_{(n-1),1} - 1) \dots (p_{(n-1),k_{n-1}} - 1)$.

At this point, note for later use that if $p$ is a prime factor of any $A_k, k \in \{1, \dots, (n-1)\}$ then $(p - 1)$ is a factor of $a_n$. Also, note that all such factors $p$ are odd, because all $A_k$ are odd.

Let $B = A_n + 2 = 2^{a_n} - 1$. If $p$ is a prime factor of any of the $A_k, k \in \{1, \dots, n-1\}$, then $p$ is a factor of $B$. Indeed, note that $a_n = b \cdot (p - 1)$ for some $b$, so $B = 2^{a_n} - 1 = 2^{b \cdot (p - 1)} - 1 = (2^b)^{p-1} - 1$, which is divisible by $p$ according to Fermat's_Little_Theorem.

It follows that $A_n = 2^{a_n} - 3$ is coprime with all $A_k, k \in \{1, \dots, (n-1)\}$. This can be justified easily, by noting that if there were a common factor $b$ between $A_n$ and an $A_k$, there would exist a prime common factor $p$. But then this $p$ would be a common factor between two consecutive odd integers $A_n$ and $B$, which is impossible.

[Revised, completed solution by pf02, December 2024]


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1971_IMO_Problems/Problem_3&oldid=237471"