9
$\begingroup$

For positive integers $n$ , define $$f(n):=\varphi(n)^{\varphi(\varphi(n))}+1$$ where $\varphi(n)$ denotes the totient function.

According to my calculation, for the following positive integers $n$ , $f(n)$ is a prime number : $$[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 97, 119, 153, 194, 195, 208, 224, 23 8, 260, 280, 288, 306, 312, 336, 360, 390, 420]$$ and upto $n=10^4$, no further prime occurs. For $n>6$ , we have $\varphi(\varphi(n))>1$ and $\varphi(n)>1$ hence $\varphi(\varphi(n))$ must be a power of $2$. The number is then a generalized Fermat-number.

Do further primes $f(n)$ exist ?

$\endgroup$
  • 1
    $\begingroup$ @paw88789 To get a prime , this must be the case. $\endgroup$ – Peter Jul 26 '18 at 16:22
  • 2
    $\begingroup$ @Joffan if $q$ is an odd prime factor of $n$ , then $a^n+1$ is divisible by $a^{n/q}+1$ $\endgroup$ – Peter Jul 26 '18 at 16:24
  • 1
    $\begingroup$ Have you looked it up in the OEIS? I just did. No relevant results. $\endgroup$ – Robert Soupe Jul 26 '18 at 18:19
  • 1
    $\begingroup$ Then I tried Select[Range[1000], PrimeQ[EulerPhi[#]^EulerPhi[EulerPhi[#]] + 1] &] in Wolfram Alpha. I probably need Mathematica if I want to confirm your assertion up to $10^4$. $\endgroup$ – Robert Soupe Jul 26 '18 at 18:22
  • 1
    $\begingroup$ @RobertSoupe : Pari/GP is a free software which is able to deal with that problem nicely. Note btw, that many $n$ have the same value $\varphi(n)$ and thus the same $\text{isprime}(f(n)$ -result, so time consumption could be much reduced when you avoid multiple computation of the $f(n)$ at different $n$ leading to the same result. $\endgroup$ – Gottfried Helms Jul 26 '18 at 20:58
0
$\begingroup$

This is mostly just a summary of what I have found that is to big for a comment.

Since $\varphi(\varphi(n))$ must be a power of $2$, $\varphi(n)=2^m p_1 p_2 p_3...p_m$. Where each of the $p_i$ is a distinct Fermat prime. Thus we have $$\varphi(n)^{\varphi(\varphi(n))}+1=(2^mp_1p_2p_3...p_m)^{2^r}+1.\tag{1}$$ We also have that $$n=2^uq_1q_2...q_sp_1^{e_1}p_2^{e_2}...p_m^{e_m}$$ where the $q_i$ are primes of the form $2^dp_i+1$, and the $e_i$ are each $0,1$ or $2$. If a $q_i$ is present in the factorization, then $e_i$ is at most $1$.

If we want to answer your question, it will probably be easiest to work with the right side of $(1)$.

$\endgroup$

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.