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

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