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 "1989 IMO Problems/Problem 5"
(→‎Solution)
 
Line 2: Line 2:
 
Prove that for each positive integer <math> n</math> there exist <math> n</math> consecutive positive integers none of which is an integral power of a prime number.
 
Prove that for each positive integer <math> n</math> there exist <math> n</math> consecutive positive integers none of which is an integral power of a prime number.
  
−
==Solution==
+
==Solution 1==
 
There are at most <math>1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)</math> 'true' powers <math>m^k , k\geq 2</math> in the set <math>\{1,2,...,n\}</math>. So when <math>p(n)</math> gives the amount of 'true' powers <math>\leq n</math> we get that <math>\lim_{n \to \infty} \frac{p(n)}{n} = 0</math>.
 
There are at most <math>1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)</math> 'true' powers <math>m^k , k\geq 2</math> in the set <math>\{1,2,...,n\}</math>. So when <math>p(n)</math> gives the amount of 'true' powers <math>\leq n</math> we get that <math>\lim_{n \to \infty} \frac{p(n)}{n} = 0</math>.
  
Line 11: Line 11:
  
 
This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [https://aops.com/community/p372297]
 
This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [https://aops.com/community/p372297]
 +
 +
==Solution 2==
 +
By Chinese Remainder theorem, there exists <math>x</math> such that:
 +
<math>x \equiv -1\;mod\;p_1 q_1\\
 +
x \equiv -2\;mod\;p_2 q_2\\
 +
x \equiv -3\;mod\;p_3 q_3\\
 +
...\newline
 +
x \equiv -n\;mod\;p_n q_n</math>
 +
Where <math>p_1, p_2, ..., p_n, q_1, q_2, ..., q_n</math> are distinct primes.
 +
The n consecutive numbers <math>x+1, x+2, ..., x+n</math> each have at least two prime factors, so none of them can be expressed as an integral power of a prime.
  
 
== See Also == {{IMO box|year=1989|num-b=4|num-a=6}}
 
== See Also == {{IMO box|year=1989|num-b=4|num-a=6}}
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 21:58, 4 July 2021

Problem

Prove that for each positive integer $n$ there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

Solution 1

There are at most $1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)$ 'true' powers $m^k , k\geq 2$ in the set $\{1,2,...,n\}$. So when $p(n)$ gives the amount of 'true' powers $\leq n$ we get that $\lim_{n \to \infty} \frac{p(n)}{n} = 0$.

Since also $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$, we get that $\lim_{n \to \infty} \frac{p(n)+\pi(n)}{n} = 0$. Now assume that there is no 'gap' of lenght at least $k$ into the set of 'true' powers and the primes. Then this would give that $\frac{p(n)+\pi(n)}{n} \geq \frac{1}{k}$ for all $n$ in contrary to the above (at east this proves a bit more).

Edit: to elementarize the $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ part: Look $\mod (k+1)!$. Then all numbers in the residue classes $2,3,4,...,k+1$ are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length $k$, there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each $(k+1)!$ numbers, again contradicting $\lim_{n \to \infty} \frac{p(n)}{n} = 0$.

This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]

Solution 2

By Chinese Remainder theorem, there exists $x$ such that: $x \equiv -1\;mod\;p_1 q_1\\ x \equiv -2\;mod\;p_2 q_2\\ x \equiv -3\;mod\;p_3 q_3\\ ...\newline x \equiv -n\;mod\;p_n q_n$ Where $p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$ are distinct primes. The n consecutive numbers $x+1, x+2, ..., x+n$ each have at least two prime factors, so none of them can be expressed as an integral power of a prime.

See Also

1989 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_IMO_Problems/Problem_5&oldid=157363"