4
$\begingroup$

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

I'm not getting a single idea of how to approach it. One I found was to show that $n$ consecutive integers should not be divisible by any prime but it didn't worked.

Thanks in advance.

$\endgroup$
3
$\begingroup$

I see there is a lot of confusion about the idea described by wythagoras. Let's consider every natural number in the interval $[n!+2,n!+n/2]$.
Suppose we want to prove that $n!+k$ from the interval, is not integral power of prime. Let's factor out the greatest power possible of smallest prime factor of $k$ and call it $q^z$.
Now $n!+k$ is either integral power of $q$ or it is not integral power of any prime at all.
Now let's consider two cases if there is another prime factor of $q$ in $n!/q^z$, then $q\mid n!/q^z$, but it does not divide $k/q^z$ so it cannot divide $n!/q^z+k/q^z$.
The other case, suppose there is no other factor of $q$ in $n!/q^z$, but this cannot be the case as we know that $k\le n/2$, there is $2k$ in the product of $n!$, i.e. $k*2k$ and $k$ ,$q^z\mid k$ we can certainly say that at least $q^{2z}\mid k*2k$, therefore $q^{2z}\mid n!$.
I hope this helps.

$\endgroup$
  • $\begingroup$ I really liked the solution. It was elegant. Thanks a lot! $\endgroup$ – Shrey May 16 '15 at 3:39
8
$\begingroup$

Consider the system of $n$ congruences

$x\equiv 0\pmod{(2)(3)}$

$x\equiv -1\pmod{(5)(7)}$

$x\equiv -2 \pmod{(11)(13)}$

and so on, up to

$x\equiv -(n-1)\pmod{(p_{2n-3})(p_{2n-2})}$

where $p_i$ is the $i$-th prime.

By the Chinese Remainder Theorem, this system of congruences has infinitely many positive solutions $x$.

If $x$ is such a solution, then $x$ is divisible by $(2)(3)$, $x+1$ is divisible by $(5)(7)$, and so on.

It follows that none of $x$, $x+1$, and so on up to $x+(n-1)$ is a prime power.

$\endgroup$
3
$\begingroup$

Hint: Look to numbers near some factorials.

Example: The numbers near $9!$:

  • $9!+2 = 2(9!/2+1)$. Since $9!$ has another factor $2$, $9!/2+1$ is odd and therefore is $9! + 2$ not a prime power. (It is divisible by $2$, but not a prime power of $2$)

  • $9!+3 = 3(9!/3+1)$. Since $9!$ has another factor $3$, $9!/3+1$ is
    not divisible by $3$ and therefore is $9! + 3$ not a prime power.
    (It is divisible by $3$, but not a prime power of $3$)

In general, you can prove that all numbers form $n!+2$ to $n!+\frac{n}{2}$ cannot be prime powers.

$\endgroup$
  • $\begingroup$ Not getting anywhere. Can you explain a bit. $\endgroup$ – Shrey May 15 '15 at 8:30
  • $\begingroup$ I edited the answer. $\endgroup$ – wythagoras May 15 '15 at 8:35
  • $\begingroup$ The two cases above do not make clear how you intend to generalize it to arbitrary $\,n.\ \ $ $\endgroup$ – Bill Dubuque May 15 '15 at 13:47
  • $\begingroup$ @BillDubuque I edited the answer. $\endgroup$ – wythagoras May 15 '15 at 14:31
  • $\begingroup$ It's still not clear. Please say how you intended the argument to work in general. $\endgroup$ – Bill Dubuque May 15 '15 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.