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

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$ ?

• As usual, questions about primes of a given form receive at least one downvote :) – Peter Aug 12 '18 at 12:03

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

• I wonder whether $$133^{133}+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits. – Peter Aug 11 '18 at 23:32
• (+1) especially because of the congruence $$\varphi(n)^{\varphi(n)}\equiv 1\mod n$$ which is a consequence of Euler's theorem and $\gcd(n,\varphi(n))=1$ – Peter Aug 11 '18 at 23:46

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]

• According to my calculations, there is no example for $n\le 20\ 000$ in the case $n^n+\varphi(n)$. Hence such an example must have more than $86\ 000$ digits, – Peter Aug 12 '18 at 17:56