If $φ(p) > φ(k)$ for $k<p$, is $p$ always a prime?

Question

So I was playing around with the Euler totient function on desmos, and found that whenever the function "spikes", we can add $1$ to it and I always found a prime number. With very powerful computers or software why can't we use this for finding prime numbers?

It's my first time on this site and the question maybe stupid but can someone can please explain? Thanks in advance!

Answer 1

Just for fun, let's rephrase this into a theorem:

Theorem: if $\phi(n)>\phi(k)$ for all $k<n$ then $\phi(n)+1$ is prime.

Lemma: if $p$ is prime then $\phi(p)>\phi(k)$ for all $k<p$

Proof:

Let $C(m,n)=1$ if $\gcd(m,n)=1$ and $C(m,n)=0$ if $\gcd(m,n)\neq1$

Therefore $$\phi(x)=\sum_{n=1}^{x-1}C(x,n)$$

Since $p$ being prime implies $\gcd(p,k)=1$

$$\implies\phi(p)=\sum_{n=1}^{x-1}\gcd(p,n)=\sum_{n=1}^{x-1}1=p-1$$

Since that is the maximal possible sum, then $\phi(p)>\phi(k)$ for all $k<p$

Therefore $\phi(n)>\phi(k)$ for all $k<n$ implies $n$ is prime.

$n$ being prime implies $\phi(n)=n-1$, therefore $\phi(n)+1$ is prime.

QED

---

As for using this to find more primes. It's no more efficient than a prime sieve. Specifically, as user21820 pointed out

$\gcd(m,n)$ with $m≤n$ takes $O(\log n)$ multiplications and divisions on operands of bit-length $O(\log n)$, and each operation on b-bit integers takes $O(b^2)$ time using schoolbook multiplication, or $O(b\log b)$ time even with state-of-the-art algorithms. So $\gcd(m,n)$ would take $O((\log n)^2⋅\log(\log n))$ time using best known algorithms. It suffices for you to just say that the summation takes $Ω(n)$ time, which is silly because prime factorization would take $O(\sqrt{n}(\log n)^2)$ time even with schoolbook algorithms.

Answer 2

Try to verify for yourself that $$ \phi(n) = n-1 $$ if and only if $n$ is a prime. From that relation you can see that you can indeed use Eulers totient function to find primes. However, it will most often be the case that the easiest way to show that $\phi(n) = n-1$ is to show that $n$ is a prime in some other way than calculating the totient function. For example using some kind of primality test: https://en.wikipedia.org/wiki/Primality_test.