Primes of the the form $(n^n +1)$

Since $15 \log_{10}15 < 18 < 16\log_{10}16$ , we are only interested in $n$ in the range $1 \le n \le 15$ .

If $n$ has an odd prime factor $p$ , so that $n = pq$ for some $q \ge 1$ , then since $n^n + 1 \; = \; n^{pq} + 1 \; = \; (n^q + 1)\sum_{j=0}^{p-1} (-1)^j n^{qj}$ we deduce that $n^n + 1$ is divisible by $n^q + 1$ and is bigger than $n^q + 1$ , and hence is not prime.

Thus the only cases we need to consider are $n = 1,2,4,8$ . The first three ( $2\,,\,5\,,\,257$ ) are prime, while $8^8 + 1 \; = \; 2^{24} + 1$ is divisible by $2^8+1$ , so is not prime. The answer is therefore $\boxed{3}$ .

First use the fact that $a^n+b^n$ is factorable if $a$ and $b$ are both odd. Then use fermat's primes.

This problem becomes trivial if we apply the overkill technique: Zsigmondy's theorem .

On the other hand, here's a similar problem that was posted last time.