The question is: for any $n\geq2$, is there always a prime $p$ satifying $\varphi(n)<p\leq 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<n$, then $n$ is prime)

  • $\begingroup$ By a simple program running on my laptop, there is no counterexample under $10^{10}$. $\endgroup$ – rqy Jul 8 at 16:26
  • $\begingroup$ 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}$. $\endgroup$ – 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)<n-\sqrt{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).

Reference: Upper bound for Euler's totient function on composite numbers

| cite | improve this answer | |
  • $\begingroup$ why "There is always a prime between $n−\sqrt{n}$ and $n$"? $\endgroup$ – rqy Jul 8 at 16:04
  • $\begingroup$ It's so hard to improve the upper bound of prime gap, I think this is not the right way (if there is a right way) $\endgroup$ – rqy Jul 8 at 16:07
  • $\begingroup$ On the other hand $\phi(n)$ can be so large for composite $n$, so it cannot be avoided, I think. $\endgroup$ – Dietrich Burde Jul 8 at 16:08
  • $\begingroup$ 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$. $\endgroup$ – rqy Jul 8 at 16:14

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.