A conjecture: for all $n\in\mathbb{N}$, the least $k>1$ such that $\phi(k)\geqslant n$ is a prime

Question

I came across a problem in a book that asked us to find the first number $n$ such that $\phi(n)\geqslant 1,000$ it turns out that the answer is 1009, which is a prime number. There were several questions of this type, and our professor conjectured that it will always be the next prime. However, no one has been able to come up with a proof for this conjecture. So, more formally the conjecture is:

For all $n\in\mathbb{N}$ the least positive integer $k\in\mathbb{N}$, with $k>1$ such that $\phi(k)\geqslant n$ is a prime.

I have worked with the Möbius Inversion function, and other minimal element contradictory proofs, but nothing has worked so far. Does anyone have any good ideas?

Answer 1

Initial response: this should follow from a fairly mild conjecture on prime gaps, that there for a prime $p \geq 127,$ there is always a prime $q$ with $p < q < p + \sqrt p.$ The last known bad one is $113,$ as $\sqrt {113} \approx 10.63,$ the sum is about $123.63,$ but the first prime after $113$ is $127.$ The things that have actually been proved of this type have exponents slightly larger then $1/2,$ plus they typically have the condition "for large enough numbers," meaning we cannot invoke these theorems directly for this problem. Edit, Komputer Kalkulation: for a prime $p \geq 2999,$ there is always a prime $q$ with $p < q < p + \frac{1 }{2} \sqrt p \;;$ kalkulated for all $p \leq 1000000.$ This slightly stronger conjecture (that it is true for all $p \geq 2999$) implies the conjecture in the original question quite directly. Plus, you can see from the Table of first 75 that this stronger conjecture holds for all $ 4 \cdot 10^{18} \geq p \geq 9551,$ and my little computer run just extends the 9551 down to 2999.

The reason this is relevant is the way $\phi$ reduces numbers. While $\phi(p) = p - 1, $ suppose we had a prime $r$ with $r^2$ of comparable size to $p.$ Then $\phi(r^2) = r^2 - r,$ which is closer to $p - \sqrt p.$ If $r^2 - r \geq N,$ we think there is going to be a $N < p < r^2.$ Similarly,for primes $r,s$ and $rs \approx p,$ we find that $\phi(rs)$ is smaller still.

So, this is a pretty reasonable conjecture. There could even be an elementary proof, hard to say.

EXERCISE: if $M \geq 4$ is not prime, does it follow that $\phi(M) \leq M - \sqrt M?$ I'm going to do a little computer run.

Komputer Kalkulation: if $M \geq 4$ is not prime, then $\phi(M) \leq M - \sqrt M,$ and equality holds only if $M = r^2$ for prime $r.$

Should not be difficult to prove the Kalkulation. EDIT: yes, this is meaning of the first displayed equation in the answer by mjqxxxx

Answer 2

Slightly too long for a comment.

One can create arbitrarily long series of integers which are not primes. Let $n \in \mathbb{N}$ and consider such a series $n, n+1, \dots, n+r$ where $n+r$ is the first prime above $n$. Suppose one can find a number $n+s$ with $s < r$ and $n+s = pq$ where $p$ and $q$ are primes. We want to choose these numbers so that

$$\phi(n+s) = \phi(pq) = (p-1)(q-1) \geq n$$

Since $pq = n+s$, this means $s+1 > p+q$ will produce a counter example.

It is not clear (to me) that this is possible. I am hopeful because the sequence $n, \dots, n+r$ can be made arbitrarily long. It is however clear that such a counter example constructed this way will be very very large.

Answer 3

If $n$ is not prime, then it has a prime factor $\le \sqrt{n}$, and so $$ \varphi(n) = n \prod_{p\;|\;n}\left(1-\frac{1}{p}\right)\le n\left(1-\frac{1}{\sqrt{n}}\right)=n-\sqrt{n}; $$ while $\varphi(n)=n-1$ if $n$ is prime.

So, fix $M$. Let $p$ be the next prime number after $M$, so $\varphi(p)=p-1\ge M$; and let $p'$ be the largest prime number $\le M$. (That is, $p$ and $p'$ are adjacent primes.) Finally, suppose that a composite $n < p$ also satisfies $\varphi(n)\ge M$. Then $$ p-\sqrt{p}>n-\sqrt{n}\ge\varphi(n)\ge M \ge p', $$ or $$ p-p'\ge \sqrt{p}. $$ If this were known to never happen for sufficiently large $p$ (i.e., if eventually $g_k < \sqrt{p_{k+1}}$, where $p_k$ is the $k$-th prime, and the prime gap $g_k\equiv p_{k+1}-p_{k}$), then your conjecture could be proven. This is a strong conjecture (although almost certainly true)... I do not believe it is even known to follow from the Riemann hypothesis. Looking at the table of prime gaps, though, there are very few counterexamples, and the only near misses for your conjecture are: $$ M=2 \qquad \varphi(3)=\varphi(4)=2; \\ M=6 \qquad \varphi(7)=\varphi(9)=6; \\ M=20 \qquad \varphi(23)=22; \varphi(25)=20; \\ M=110 \qquad \varphi(113)=112; \varphi(121)=110. $$