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

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 ?

• Of course, it ought to be the case that $p \neq k$. Otherwise, $p^p + k = p^p + p = p(p^{p-1} + 1)$ will be composite. – Arnie Bebita-Dris May 18 '19 at 9:07
• @JoseArnaldoBebita-Dris This can be strengthened : $\gcd(p,k)=1$ is necessary to give a prime. – Peter May 18 '19 at 9:08

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

• Superb answer (+1 and accept). – Peter May 18 '19 at 11:24

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