Difference between revisions of "1989 IMO Problems/Problem 5"
m (Fixed LaTeX errors.) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | + | 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 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>. | ||
+ | |||
+ | Since also <math>\lim_{n \to \infty} \frac{\pi(n)}{n} = 0</math>, we get that <math>\lim_{n \to \infty} \frac{p(n)+\pi(n)}{n} = 0</math>. Now assume that there is no 'gap' of lenght at least <math>k</math> into the set of 'true' powers and the primes. Then this would give that <math>\frac{p(n)+\pi(n)}{n} \geq \frac{1}{k}</math> for all <math>n</math> in contrary to the above (at east this proves a bit more). | ||
+ | |||
+ | Edit: to elementarize the <math>\lim_{n \to \infty} \frac{\pi(n)}{n} = 0</math> part: | ||
+ | Look <math>\mod (k+1)!</math>. Then all numbers in the residue classes <math>2,3,4,...,k+1</math> are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length <math>k</math>, there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each <math>(k+1)!</math> numbers, again contradicting <math>\lim_{n \to \infty} \frac{p(n)}{n} = 0</math>. | ||
+ | |||
+ | 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 the [[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 <math>n</math> 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. | ||
+ | ==Solution 3== | ||
+ | OG, If <math>n=1</math>, then select any composite number | ||
+ | <math>Claim:</math> If <math>n>1</math>, then the consectutive number <math>(2n+3)!+2, (2n+3)!+3 \cdots (2n+3)!+(n+1)</math>, give the desired <math>n</math> consecutive numbers as each of the numbers are divisible by at least 2 primes. | ||
+ | Proof: Each of the numbers are <math>(2n+3)!+k, 2 \leq k \leq n+1</math>, Now since <math>2k \leq (2n+3)! \implies k^2|(2n+3)</math>, Thus <math>(2n+3)!+k= k(kq+1)</math>, which clearly has atleast 2 prime divisors. Hence DONE, OG | ||
+ | |||
+ | |||
+ | == See Also == {{IMO box|year=1989|num-b=4|num-a=6}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 01:55, 24 August 2024
Problem
Prove that for each positive integer there exist
consecutive positive integers none of which is an integral power of a prime number.
Solution 1
There are at most 'true' powers
in the set
. So when
gives the amount of 'true' powers
we get that
.
Since also , we get that
. Now assume that there is no 'gap' of lenght at least
into the set of 'true' powers and the primes. Then this would give that
for all
in contrary to the above (at east this proves a bit more).
Edit: to elementarize the part:
Look
. Then all numbers in the residue classes
are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length
, there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each
numbers, again contradicting
.
This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]
Solution 2
By the Chinese Remainder Theorem, there exists such that:
where
are distinct primes.
The
consecutive numbers
each have at least two prime factors, so none of them can be expressed as an integral power of a prime.
Solution 3
OG, If , then select any composite number
If
, then the consectutive number
, give the desired
consecutive numbers as each of the numbers are divisible by at least 2 primes.
Proof: Each of the numbers are
, Now since
, Thus
, which clearly has atleast 2 prime divisors. Hence DONE, OG
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 |