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 ?

  • 1
    $\begingroup$ 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. $\endgroup$ – Arnie Bebita-Dris May 18 '19 at 9:07
  • 2
    $\begingroup$ @JoseArnaldoBebita-Dris This can be strengthened : $\gcd(p,k)=1$ is necessary to give a prime. $\endgroup$ – 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$.

  • $\begingroup$ Superb answer (+1 and accept). $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.