None of which is an integral power of a prime number

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Nov 19, 2005, 11:22 AM • 2 Y

Y by Adventure10, Mango247

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

This post has been edited 1 time. Last edited by orl, Sep 18, 2008, 4:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#2 h Nov 19, 2005, 12:08 PM • 1 Y

Y by Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

grobber

7849 posts

grobber

#3 h Nov 19, 2005, 1:15 PM • 16 Y

Y by shiningsunnyday, myh2910, Pluto1708, Adventure10, paccongnong19hy, Mango247, kiyoras_2001, Funcshun840, alizoratiopour, and 7 other users

Or we can just choose $2n$ distinct primes $\{p_i\}_i,\{q_i\}_i,\ i=\overline{1,n}$ , and take a positive integer $k$ such that $k\equiv -i\pmod{p_iq_i},\ \forall i\in\overline{1,n}$ , which must exist by the Chinese Remainder Theorem. The numbers $k+1,k+2,\ldots,k+n$ will do the trick.

A little simpler, huh?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dblues

203 posts

dblues

#4 h Nov 20, 2005, 2:33 AM • 15 Y

Y by devarshruparelia, Kezer, myh2910, Pluto1708, gabrupro, Adventure10, ZHEKSHEN, rayfish, Mango247, ehuseyinyigit, Funcshun840, and 4 other users

Well, a much simpler solution would be to consider the set of $n$ integers $\{ [(n+1)!]^2 + 2, [(n+1)!]^2 + 3, \ldots , [(n+1)!]^2 + (n+1) \}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vyfukas

165 posts

vyfukas

#5 h Dec 24, 2013, 9:59 AM • 3 Y

Y by ZHEKSHEN, Adventure10, Mango247

I have found the same solution as dblues and I wonder isn't it too easy for IMO #5?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#6 h Dec 24, 2013, 10:20 AM • 4 Y

Y by myh2910, Adventure10, Mango247, and 1 other user

Extension: Replace prime with power of any integer.

Hint

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vyfukas

165 posts

vyfukas

#7 h Dec 24, 2013, 10:38 AM • 2 Y

Y by Adventure10, Mango247

But then any integer is a power of itself.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Binomial-theorem

3982 posts

Binomial-theorem

#8 h Dec 24, 2013, 11:01 AM • 2 Y

Y by Adventure10, Mango247

I mean perfect power (i.e the exponent is greater than one).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#9 h Dec 24, 2013, 12:06 PM • 2 Y

Y by Adventure10 and 1 other user

By taking (by CRT) $x_0$ a positive integer solution of the system of congruences $x+k\equiv p_k\pmod{p_k^2}$ , $1\leq k \leq n$ , and $x = x_0 + \prod_{k=1}^n p_k^2$ , we also guarantee $x+k$ is composite for all $k$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Konigsberg

2239 posts

Konigsberg

#10 h Jul 2, 2014, 7:27 PM • 2 Y

Y by Adventure10, Mango247

dblues wrote:

Well, a much simpler solution would be to consider the set of $n$ integers $\{ [(n+1)!]^2 + 2, [(n+1)!]^2 + 3, \ldots , [(n+1)!]^2 + (n+1) \}$ .

Not to nitpick, but I think that you should prove that they are all NOT perfect powers of a prime number.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JuanOrtiz

366 posts

JuanOrtiz

#11 h Jan 24, 2015, 7:32 PM • 1 Y

Y by Adventure10

CRT..........

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FalloutBoy

20 posts

FalloutBoy

#12 h Jan 25, 2015, 3:20 AM • 2 Y

Y by Adventure10, Mango247

never mind

This post has been edited 1 time. Last edited by FalloutBoy, Jan 25, 2015, 1:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ComplexPhi

455 posts

ComplexPhi

#13 h Jan 25, 2015, 9:37 AM • 4 Y

Y by gabrupro, Illuzion, Adventure10, Mango247

I will explain dblues's solution .
Let's assume that one of the numbers is the power of a prime.
Let it be $[(n+1)!]^2+i=p^k$ with $p$ prime and $2\leq i\leq n+1$ .
From this we get that $i$ divides $p^k$ so $i=p^l$ with $l\geq 1$ .
So $p\leq i\leq n+1$ . Obviously $k=v_p([(n+1)!]^2+i)=\min(v_p([(n+1)!]^2),v_p(i))=v_p(i)=l$
$i=p^l=p^k=[(n+1)!]^2+i$ a contradiction.
$v_p(x)$ is the exponent of $p$ in $x$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aleph_zero

18 posts

aleph_zero

#14 h Jan 25, 2015, 10:05 AM • 1 Y

Y by Adventure10

How do we get $(n+1)!^2+i=p^k\Rightarrow i\mid p^k$ ??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

utkarshgupta

2280 posts

utkarshgupta

#15 h Jan 25, 2015, 10:21 AM • 1 Y

Y by Adventure10

aleph_zero wrote:

How do we get $(n+1)!^2+i=p^k\Rightarrow i\mid p^k$ ??

Because $i|(n+1)! \implies i|(n+1)!^2+i \implies i|p^k$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NguyenDung

43 posts

NguyenDung

#16 h Jun 8, 2015, 1:17 PM • 1 Y

Y by Adventure10

My solution
Let ${p_1},{p_2},...,{p_{2n}}$ be $2n$ prime intergers
Consider the system of equations
$x \equiv - 1\left( {\bmod {p_1}} \right)$
$x \equiv - 1\left( {\bmod {p_2}} \right)$
$x \equiv - 2\left( {\bmod {p_3}} \right)$
$x \equiv - 2\left( {\bmod {p_4}} \right)$
$..$ .
$x \equiv - 1\left( {\bmod {p_{2n - 1}}} \right)$
$x \equiv - 1\left( {\bmod {p_{2n}}} \right)$
By CRT, the system have one $x$ satisfies
So, $x + i \vdots {p_{2i - 1}},{p_{2i}}$ , $i = \overline {1,n}$
....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Xxenia_Sh

6 posts

Xxenia_Sh

#17 h Jun 3, 2020, 6:39 PM • 1 Y

Y by valsidalv007

Let us take any $a\in\mathbb{N}$ and consider $n$ consecutive integers $a+1,..., a+n$ . If none of this numbers is an integral power of a prime number, then we are done. Now suppose ${p_1}^{a_1}<...<{p_k}^{a_k}$ are all the numbers (among $a+1,..., a+n$ ) which are integral powers of prime numbers ( $p_1, ...,p_k$ - prime numbers). I take $N=s*{p_1}^{a_1+1}*...*{p_k}^{a_k+1}$ ( I choose $s\in\mathbb{N}$ so that $N>(a+n)$ ) and prove that none of $n$ consecutive integers $N!+a+1,..., N!+a+n$ is an integral power of a prime number. There are 2 cases:
1. $a+i$ ( $n\geq i\geq 1$ ) isn't an integral power of a prime number. $(N!+a+i )\vdots{(a+i)}$ , so $N!+a+i$ isn't an integral power of a prime number.
2. $a+i={p_j}^{a_j}$ ( $n\geq i\geq 1$ ) for some $j$ , $k\geq i\geq 1$ . Suppose $(N!+a+i )=p^t$ for some prime number $p$ and $t\in\mathbb{Z}$ . Note that $(N!+a+i )\vdots{(a+i)}$ , so $p={p_j}$ . Also $N!\vdots N\vdots {({p_j}^{a_j+1})}$ and $a+i={p_j}^{a_j}$ so ${p_j}^{a_j+1}$ doesn't divide $N!+a+i$ , so ${p_j}^{a_j}\geq N!+a+i$ . Contradiction.
So $N!+a+i$ isn't an integral power of a prime number for $n\geq i\geq 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PCChess

548 posts

PCChess

#18 h Oct 8, 2020, 3:10 AM

Y by

The problem is essentially asking to find a natural number $m$ such that $m, m+1, \dots, m+n-1$ are not powers of any prime.
Consider the list of primes $\{p_1, p_2, p_3, \dots\}$ . Simply pick $m$ such that $m$ satisfies the following congruences.

$\begin{align*} m \equiv 0 \pmod {p_1p_2} \\ m+1 \equiv 0 \pmod {p_3p_4} \\ \vdots \\ m+n-1 \equiv 0 \pmod {p_{2n-1}p_{2n}} \\ \end{align*}$
A solution exists by CRT. Further, each number in the sequence $\{m, m+1, \dots, m+n-1\}$ is divisible by the product of $2$ primes, so this $m$ works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathematicsislovely

245 posts

Mathematicsislovely

#19 h Feb 17, 2021, 9:31 PM • 2 Y

Y by amar_04, SSaad

Let $p_1,p_2,p_3,\dots,p_n$ are $N$ prime numbers.By CRT we can find arbitrary large $x$ such that:
$\begin{align*} x &\equiv p_1-1 \pmod{p_1^2} \\ x &\equiv p_2-2 \pmod{p_2^2} \\ &\phantom\equiv\vdots \\ x &\equiv p_n-n \pmod{p_n^2}. \end{align*}$ But then $x+i$ is divisible by $p_i$ but not by $p_i^2$ .Now take $x$ sufficiently large in that particular residue class $\pmod{p_1p_2\dots p_N}$ so that $x+i\ne p_i$ .
$\square$

This post has been edited 2 times. Last edited by Mathematicsislovely, Feb 18, 2021, 8:50 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FibonacciMoose

54 posts

FibonacciMoose

#20 h Apr 22, 2021, 1:48 PM

Y by

let $\{p_i\}$ and $\{h_i\}$ be two sequences of prime numbers and $\{p_i\} \cap \{h_i\}=\emptyset$
Hence we are looking for $x$ the solutions to this system
$\begin{align*} x \equiv i \pmod{p_i\cdot h_i} \end{align*}$ for $i =\{1, 2,... ,n\}$ and by the Chinese Remainder Theorem it has a solution

This post has been edited 1 time. Last edited by FibonacciMoose, Apr 22, 2021, 1:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TortilloSquad

305 posts

TortilloSquad

#21 h Jul 7, 2021, 2:58 AM • 1 Y

Y by animath_314159

Clearly, the product of two distinct primes cannot be the power of a prime, and if an integer is a multiple of a product of two distinct primes it also cannot be the power of a prime. The problem statement is equivalent to the following system of congruences:

$\begin{align*} x &\equiv 0 \pmod {p_1p_2} \\ x+1 &\equiv 0 \pmod {p_3p_4} \\ \cdots \\ x+n-1 &\equiv 0 \pmod {p_{2n-1}p_{2n}} \\ \end{align*}$
which can be rewritten as

$\begin{align*} x &\equiv 0 \pmod {p_1p_2} \\ x &\equiv -1 \pmod {p_3p_4} \\ \cdots \\ x &\equiv -n+1 \pmod {p_{2n-1}p_{2n+1}} \\ \end{align*}$ .

By CRT this system has a solution $x$ , which means those consecutive integers exist, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

554183

484 posts

554183

#22 h Nov 16, 2021, 1:45 PM

Y by

Choose the first $2n$ prime numbers, and choose $a$ satisfying $a \equiv{-k} \pmod{p_{2k-1}p_{2k}}$ for all $k$ (Which clearly exists by CRT). Then $a+1, \dots, a+n$ Is a valid set satisfying the desired conditions.

This post has been edited 1 time. Last edited by 554183, Nov 16, 2021, 1:49 PM
Reason: I was high

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SPHS1234

466 posts

SPHS1234

#23 h Dec 6, 2021, 11:27 AM

Y by

Take $a=(2n)!-n$ Then $<a+i>_{0\leq I \leq n-1}$ works

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#24 h May 25, 2022, 9:15 AM

Y by

Let $p_1,\dots, p_{2i}$ be a sequence of $2i$ distinct primes. By CRT, there exists a $q$ such that $\begin{align*} &p_1p_2\mid q+1 \\ \vdots \\ &p_{2i-1}p_{2i} \mid q+i, \end{align*}$ the claim follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8881 posts

HamstPan38825

#25 h Jul 19, 2022, 11:40 PM

Y by

By CRT there exists a positive integer $m$ such that $m \equiv -i \pmod {p_{2i-1}p_{2i}}$ for all positive integers $i$ , where $p_i$ denotes the $i$ th prime. Then the $n$ integers not including $m$ immediately succeeding it work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

th1nq3r

146 posts

th1nq3r

#26 h Jul 21, 2022, 11:32 PM

Y by

Proof of IMO 1989

This post has been edited 2 times. Last edited by th1nq3r, Jul 23, 2022, 7:11 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

torch

1017 posts

torch

#27 h Jun 23, 2024, 9:13 PM

Y by

By CRT, there exists an integer $x$ such that:
$\begin{cases} x \equiv -1 \pmod{p_1 p_2} \\ x \equiv -2 \pmod{p_3 p_4} \\ \dots \\ x \equiv -n \pmod{p_{2n-1}p_{2n}}. \end{cases}$ Consider the sequence $x+1, x+2, \dots, x+n$ . Each of these integers have two prime factors. Therefore, they cannot be expressed as a power of a single prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AMC8-HH

41 posts

AMC8-HH

#28 h Jun 23, 2024, 9:20 PM

Y by

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zhoujef000

327 posts

zhoujef000

#29 h Oct 14, 2024, 7:54 PM

Y by

why is this so ez (I hope this works)

For all positive integers $i,$ let $p_i$ be the $i$ th positive prime, so for example, $p_1=2$ and $p_2=3.$ Also, define $\nu_p(q)$ to be the exponent of the largest power of $p$ dividing $q$ for all positive integers $q$ and all primes $p.$

Note that the elements of $\{p_1^2,p_2^2,\dots,p_n^2\}$ are pairwise relatively prime. Thus, by CRT, there exists infinitely many positive integers $m$ such that the following system holds:
$\begin{align*} m&\equiv p_1\pmod{p_1^2}\\ m+1&\equiv p_2\pmod{p_2^2}\\ m+2&\equiv p_3\pmod{p_3^2}\\ &\vdots \\ m+n-1&\equiv p_n\pmod{p_n^2}.\\ \end{align*}$ Since there are infinitely many positive integer values of $m$ that satisfies this, there must exist a positive $m_1$ that satisfies this such that the following series of inequalities all hold:
$\begin{align*} m_1&>p_1\\ m_1+1&>p_2\\ m_1+2&>p_3\\ &\vdots \\ m_1+n-1&>p_n.\\ \end{align*}$ Assume for the sake of contradiction that there exists an integer $0\leq k\leq n-1$ such that $m_1+k$ is a perfect power of a prime. Then, since $m_1+k\equiv p_{k+1}\pmod{p_{k+1}^2},$ $\nu_{p_{k+1}}(m_1+k)=1,$ so $m_1+1$ is a perfect power of $p_{k+1},$ and furthermore, $m_1+k=p_{k+1}>p_{k+1},$ a contradiction.

Thus, there does not exist an integer $0\leq k\leq n-1$ such that $m_1+k$ is a perfect power of a prime, and thus $\{m_1,m_1+1,m_1+2,\dots, m_1+n-1\}$ is a set of $n$ consecutive positive integers such that none of them are perfect powers of a prime, as desired. $\Box$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

1016 posts

AshAuktober

#30 h Oct 17, 2024, 10:04 AM

Y by

The numbers $k!+2, k!+3, \dots, k! + \lfloor \frac k2 \rfloor$ work for large $k$ .

Z K Y