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

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

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