Is there any $k$ , for which we can prove that $n^n+k$ is never prime?

Question

Is there any positive integer $k$, such that we can prove that $n^n+k$ is not prime for any positive integer $n$ ?

$$n^n+1805$$ has a prime factor not exceeding $43$ up to $n=1805$. However, for the multiples of $1806$ this is in general no more the case.

I think that for no $k$, $n^n+k$ must have a "small" factor for all $n$.

Is this true, and if yes, does this destroy any hope for a proof ?

Answer 1

The sequence consisting of smallest $n$ depending on $k$ is on OEIS as A087037. As stated on the page, for $k=(6m-1)^3$ there is no such $n$. For completeness I repeat the proof here.

Let $k=(6m-1)^3$ and consider $N=n^n+k$. For $n$ odd, $N$ is even, hence composite. If $3\mid n$, then $N$ is a sum of cubes, hence composite, since $a^3+b^3$ factors as $(a+b)(a^2-ab+b^2)$. Finally, if $n$ is even but not divisible by $3$, $$n^n+k\equiv(\pm 1)^n+(-1)^3\equiv 1-1\equiv 0\pmod 3$$ and hence is composite.

This method gives $k=125$ as the least number for which we know $n$ doesn't exist, but as the OEIS entry notes, existence of $n$ is unknown for many smaller $k$, the least being $k=8$.

Answer 2

Not an answer, but a method how to find some "good" $k$ (and perhaps this is how you found $k=1805$).

Suppose that for some $m$ we already know that $$\tag1n^n+k\text{ is prime}\implies m\mid n.$$ Let $q$ be a prime divisor of $k+1$ and suppose that $q-1\mid m$ and $q\nmid m$. Then $n^n+k$ can only be prime if $q\mid n$. Indeed, in all other cases we have (as we can assume $q-1\mid m\mid n$) $$n^n=\left(n^{q-1}\right)^{\frac n{q-1}}\equiv 1\pmod q$$ and so $q\mid n^n+k$. Thus except in the trivial case $k=q-1$, $n=1$, we see that $n^n+k$ is not prime. It follows that in $(1)$, we can replace $m$ with $qm$.

Initially, $(1)$ holds for $m=1$, no matter what $k$ we use. Hence if $k+1$ is even, we can use the above to improve this to $m=2$. Then with $q=3$, we can improve this to $m=6$ as long as $k\equiv -1\pmod 6$. Next we can use $q=7$ to improve this to $m=42$ provided $k\equiv -1\pmod{42}$. Then using $q=43$ to $m=1806$ provided $k\equiv -1\pmod {1806}$. Unfortunately, $1807=13\cdot 139$ is not prime and in fact there is no additional prime $q$ with $q-1\mid 1806$. Interestingly, we have reconstructed the finite OEIS sequence A014117 along the way. But it seems that $k=1805$ is the largest $k$ for which we can easily show that $(1)$ holds with $m=k+1$.