# Are there further primes of the form $\varphi(n)^{\varphi(\varphi(n))}+1$?

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 ?

• @paw88789 To get a prime , this must be the case. – Peter Jul 26 '18 at 16:22
• @Joffan if $q$ is an odd prime factor of $n$ , then $a^n+1$ is divisible by $a^{n/q}+1$ – Peter Jul 26 '18 at 16:24
• Have you looked it up in the OEIS? I just did. No relevant results. – Robert Soupe Jul 26 '18 at 18:19
• 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$. – Robert Soupe Jul 26 '18 at 18:22
• @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. – Gottfried Helms Jul 26 '18 at 20:58

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