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

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!

• What do you mean by "spikes"? Jul 25, 2020 at 7:42
• I'm sorry I can't objectively describe what a spike is, but I hope by looking at this graph you get what I'm trying to say: desmos.com/calculator/kxwdny3urj Jul 25, 2020 at 7:44
• Ah I see, a "spike" is at $x_0$ when $\phi(x_0)$ is larger than all $\phi(x):x<x_0$ Jul 25, 2020 at 7:48
• @BrainNuke Welcome to Math SE. If I understand correctly, this behavior is due to one of the ways Euler's totient function is computed. You see a "spike" because Euler's totient function $\phi(n)$ counts the # of integers less than $n$ which are relatively prime to $n$. This will be less than $n$, with the maximum ratio & value occurring when there is a minimum # which are not relatively prime, i.e., when $n$ is prime so there are none at all. Thus, $\phi(n) = n-1$ for $n$ prime gives largest value. Jul 25, 2020 at 7:51
• How do you compute $\phi(n)$ (faster than factorizing $n$ into primes and in particularly checking on the way whether $n$ is prime)? Jul 25, 2020 at 8:10

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.

• Thank you! I can understand its use as a primality test, but graphically it feels like you can find new primes using it. Is there any problem, drawback, or is it just very inefficient? Jul 25, 2020 at 7:56
• I think it is just very inefficient, but it of course depends on how you choose to calculate the totient function. Jul 25, 2020 at 7:57
• To graph it, you need to compute it in the first place. But primality testing or sieve methods are much better for finding primes.
– qwr
Jul 25, 2020 at 8:12
• @BrainNuke: What you are missing here is that you have to compute $φ(p)$ in the first place before you can even begin to compare its value to anything else, much less observe a "spike". But mathematically it is easy to prove that such computation is at least as difficult as determining whether $p$ is a prime or not! And so there is no hope in using this "spike" feature to find big primes any faster than just randomly testing big numbers for primality. Jul 25, 2020 at 16:19

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

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

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

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

Therefore $$\phi(n)>\phi(k)$$ for all $$k 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.

• Your complexity bounds are incorrect. When talking about big primes, you need to use arbitrary precision, so you cannot just say $\gcd(m,n)$ takes $O(\log n)$ time because each operation is no longer $O(1)$ time. Even if you are dealing with a word-sized integer $n$, the trivial prime factorization algorithm (checking factors up to square-root) takes $O(\sqrt{n})$ time, and computing $φ(n)$ takes only $O(\sqrt{n})$ time (since there are $O(\log n)$ prime factors), so why even bother with the useless summation identity? Jul 25, 2020 at 16:24
• Okay thanks! So then my remark of the uselessness of that summation pertains only to the asker's question. But please do fix your answer with respect to the time complexity of $\gcd$ as mentioned in my first comment. Off-topic, but IE and MS-Outlook at used by professionals, but they are both very unsafe. =P Jul 26, 2020 at 9:29
• It's actually less. $\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. Jul 26, 2020 at 11:20
• You can check this wikipedia page for the state-of-the-art time complexity results for common mathematical operations. Jul 26, 2020 at 11:22
• Haha it is great. =) Jul 26, 2020 at 11:27