2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "spikes"? $\endgroup$ – Graviton Jul 25 at 7:42
  • 1
    $\begingroup$ 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 $\endgroup$ – BrainNuke Jul 25 at 7:44
  • 1
    $\begingroup$ Ah I see, a "spike" is at $x_0$ when $\phi(x_0)$ is larger than all $\phi(x):x<x_0$ $\endgroup$ – Graviton Jul 25 at 7:48
  • 3
    $\begingroup$ @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. $\endgroup$ – John Omielan Jul 25 at 7:51
  • 3
    $\begingroup$ How do you compute $\phi(n)$ (faster than factorizing $n$ into primes and in particularly checking on the way whether $n$ is prime)? $\endgroup$ – Hagen von Eitzen Jul 25 at 8:10
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – BrainNuke Jul 25 at 7:56
  • 3
    $\begingroup$ I think it is just very inefficient, but it of course depends on how you choose to calculate the totient function. $\endgroup$ – Frederik Ravn Klausen Jul 25 at 7:57
  • 3
    $\begingroup$ To graph it, you need to compute it in the first place. But primality testing or sieve methods are much better for finding primes. $\endgroup$ – qwr Jul 25 at 8:12
  • $\begingroup$ @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. $\endgroup$ – user21820 Jul 25 at 16:19
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user21820 Jul 25 at 16:24
  • 1
    $\begingroup$ 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 $\endgroup$ – user21820 Jul 26 at 9:29
  • 1
    $\begingroup$ 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. $\endgroup$ – user21820 Jul 26 at 11:20
  • 1
    $\begingroup$ You can check this wikipedia page for the state-of-the-art time complexity results for common mathematical operations. $\endgroup$ – user21820 Jul 26 at 11:22
  • 1
    $\begingroup$ Haha it is great. =) $\endgroup$ – user21820 Jul 26 at 11:27

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.