Difference between revisions of "1971 IMO Problems/Problem 3"

Latest revision as of 17:03, 21 December 2024

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]

@@ Line 1: / Line 1: @@
-Prove that the set of integers of the form 2^k - 3(k = 2; 3; ...) contains an
+==Problem==
-infinite subset in which every two members are relatively prime.
+Prove that the set of integers of the form <math>2^k - 3(k = 2; 3; \cdots)</math> contains an infinite subset in which every two members are relatively prime.
+==Solution==
+Wlog, assume <math>a_{n}\ge 3</math>. Then say <math>p_{1}, p_{2}, \ldots, p_{k}\in \mathbb{N}</math> are all the (pairwise distinct) primes dividing <math>2^{a_{n}}-3</math> and let <math>a_{n+1}= a_{n}\cdot \prod_{i=1}^{k}(p_{i}-1)</math>. Obviously <math>p_{i}</math> is odd, for any <math>i \in \overline{1,k}</math>. So <math>\prod_{i=1}^{k}p_{i}</math> divides <math>2^{a_{n+1}}-1</math>, by Fermat's little theorem, and <math>\gcd(2^{a_{n+1}}-3, 2^{a_{n}}-3) = 1</math>. Now, by induction, it follows <math>\gcd(2^{a_{m}}-3, 2^{a_{n}}-3) = 1</math>, for any distinct <math>m, n \in \mathbb{N}</math>.
+The above solution was posted and copyrighted by s.tringali. The original thread for this problem can be found here: [https://aops.com/community/p865975]
+==Remarks (added by pf02, December 2024)==
+. 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
+<math>\gcd(2^{a_m} - 3, 2^{a_n} - 3) = 1</math>, for any distinct
+<math>m, n \in \mathbb{N}</math>".  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.
+. Below, I will re-phrase the solution, and complete it.
+==Solution revised and completed==
+Denote <math>A_n = 2^{a_n} - 3</math>.  The plan is to construct recursively
+a sequence <math>a_1 < a_2 < \dots < a_n < \dots</math> such that <math>A_n</math>
+and <math>A_k</math> are relatively prime for all <math>k < n</math>.
+Let <math>a_1 = 3</math>. (Note that any other number <math>> 3</math> would serve just
+as well.)
+Let <math>p_{1,1}, \dots, p_{1,k_1}</math> be all the prime factors of
+<math>A_1 = 2^{a_1} - 3</math>.  (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, <math>k_1 = 1</math> and <math>p_{1,1} = 5</math> since we took <math>a_1 = 3</math>.
+Define <math>a_2 = a_1 (p_{1,1} - 1) \dots (p_{1,k_1} - 1)</math>.  In
+our case <math>a_2 = 3 (5 - 1) = 12</math>.
+Define <math>\{a_n\}</math> recursively: let
+<math>\{p_{(n-1),1}, \dots, p_{(n-1),k_{n-1}}\}</math> be all the prime factors
+of <math>A_{n-1} = 2^{a_{n-1}} - 3</math>.  (Note again that we don't care
+whether factors are repeated or not.)  Let us take
+<math>a_n = a_{n-1} (p_{(n-1),1} - 1) \dots (p_{(n-1),k_{n-1}} - 1)</math>.
+At this point, note for later use that if <math>p</math> is a prime factor of
+any <math>A_k, k \in \{1, \dots, (n-1)\}</math> then <math>(p - 1)</math> is a factor of
+<math>a_n</math>.  Also, note that all such factors <math>p</math> are odd, because all
+<math>A_k</math> are odd.
+Let <math>B = A_n + 2 = 2^{a_n} - 1</math>.  If <math>p</math> is a prime factor of any
+of the <math>A_k, k \in \{1, \dots, n-1\}</math>, then <math>p</math> is a factor of
+<math>B</math>. Indeed, note that <math>a_n = b \cdot (p - 1)</math> for some <math>b</math>, so
+<math>B = 2^{a_n} - 1 = 2^{b \cdot (p - 1)} - 1 = (2^b)^{p-1} - 1</math>,
+which is divisible by <math>p</math> according to [[Fermat's_Little_Theorem]].
+It follows that <math>A_n = 2^{a_n} - 3</math> is coprime with all
+<math>A_k, k \in \{1, \dots, (n-1)\}</math>.  This can be justified easily,
+by noting that if there were a common factor <math>b</math> between <math>A_n</math>
+and an <math>A_k</math>, there would exist a prime common factor <math>p</math>.  But
+then this <math>p</math> would be a common factor between two consecutive
+odd integers <math>A_n</math> and <math>B</math>, which is impossible.
+[Revised, completed solution by pf02, December 2024]
+== See Also == {{IMO box|year=1971|num-b=2|num-a=4}}

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