Primes of the form $\ \varphi(n)^{\varphi(n)}+n\ $ or $\ n^n+\varphi(n)\ $ for composite $n$?

Question

This question :

Do further prime numbers of the form $n^n+\varphi(n)$ exist?

deals about prime numbers of the form $$n^n+\varphi(n)$$

I know no composite number $n$, such that this expression is prime.

Strangely, I neither know a composite $n$ such that $$\varphi(n)^{\varphi(n)}+n$$ is prime. This expression is prime for $n=1,2,3,7,463$ and no other $n\le 1\ 000$.

Is it a coincidence that I did not find a composite number $n$ such that either expression is a prime, or can it be proven that we never get a prime for composite $n$ ?

Answer 1

Partial answer.

Theorem: Any group of order $n$ is cyclic $\Longleftrightarrow \gcd(n,\varphi(n))=1$

It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+\varphi(n)$ and $\varphi(n)^{\varphi(n)}+n$ is a prime.

This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3\times 5$ with $3\not\mid (5-1)$). See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $\varphi(n)^{\varphi(n)}\equiv 1\bmod n$.

Answer 2

The expression $$\varphi(n)^{\varphi(n)}+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+\varphi(n)$ I still do not know an example.

Smallest current candidate : $n=14\ 199$ ($58\ 958$ digits)

Candidates (no prime factor below $10^8$) :

[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14 521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089 , 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1 5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596 7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511, 16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167 39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973, 17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17 377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953 , 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1 8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892 9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231, 19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195 37, 19653, 19699, 19759, 19769, 19843, 19967]