Difference between revisions of "1971 IMO Problems/Problem 3"
(Created page with "Prove that the set of integers of the form 2^k - 3(k = 2; 3; ...) contains an infinite subset in which every two members are relatively prime.") |
|||
Line 1: | Line 1: | ||
− | Prove that the set of integers of the form 2^k - 3(k = 2; 3; | + | ==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] | ||
+ | |||
+ | == See Also == {{IMO box|year=1971|num-b=2|num-a=4}} |
Latest revision as of 13:58, 29 January 2021
Problem
Prove that the set of integers of the form contains an infinite subset in which every two members are relatively prime.
Solution
Wlog, assume . Then say are all the (pairwise distinct) primes dividing and let . Obviously is odd, for any . So divides , by Fermat's little theorem, and . Now, by induction, it follows , for any distinct .
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 |