# Existence of a prime in $(\phi(n), n]$

The question is: for any $$n\geq2$$, is there always a prime $$p$$ satifying $$\varphi(n)?

Here $$\varphi(n)$$ is the Euler totient function.

We know that there is always a prime between $$n-O(n^\theta)$$ and $$n$$, where $$\theta$$ can be $$0.525$$ (Wiki: Prime gap). Under Riemann hypothesis, one can improve this bound to $$O(\sqrt n\log^2n)$$. But on the other hand, there are infinite many $$n$$ such that $$\phi(n)\geq n-C\sqrt n$$ for some constant $$C$$ (just choose $$n=p(p+k)$$ where $$p$$ and $$p+k$$ are both prime; for some $$k$$ these $$p$$ are infinite). So these upper bound for prime gap don't help.

So can we prove this propsition, or give a counterexample? (or give a evidence to explan why is this hard to prove, maybe?)

(The propsition is equivalent to: if $$\varphi(n)>\varphi(k)$$ for all $$1\leq k, then $$n$$ is prime)

• By a simple program running on my laptop, there is no counterexample under $10^{10}$. – rqy Jul 8 at 16:26
• Also, there is always a prime in the interval $[n-\sqrt{n},n]$ for all $5504 \leq n \leq 4 \cdot 10^{18}$. Hence there is no counterexample under $4\cdot 10^{18}$. – Dietrich Burde Jul 9 at 11:57

For prime numbers $$n$$ the claim is trivial. If $$n$$ is composite then we have the upper bound $$\phi(n) If we can show that there is always a prime between $$n-\sqrt{n}$$ and $$n$$, for $$n\ge 3$$, then the claim follows. Unfortunately this is not yet clear, see At least one prime between N and N-(sqrtN).
• why "There is always a prime between $n−\sqrt{n}$ and $n$"? – rqy Jul 8 at 16:04
• On the other hand $\phi(n)$ can be so large for composite $n$, so it cannot be avoided, I think. – Dietrich Burde Jul 8 at 16:08
• But maybe we can divide all natural numbers to several sorts and prove it in some steps. Not all $n-\varphi(n)$ is about $\sqrt n$. – rqy Jul 8 at 16:14