Find all primes of the form $n^n + 1$ less than $10^{19}$ Find all primes of the form $n^n + 1$ less than $10^{19}$
The first two primes are obvious: $n = 1, 2$ yields the primes $2, 5$. After that, it is clear that $n$ has to be even to yield an odd number.
So, $n = 2k \implies p = (2k)^{2k} + 1 \implies p-1 = (2k)^{k^2} = 2^{k^2}k^{k^2}$. All of  these transformations don't seem to help. Is there any theorem I can use? Or is there something I'm missing?

in $n^n+1$, it is algebraicly composite if n is not a power of 2.  So you're left with which powers of 2. work.
In the case where n is not $1$or of the form $2^{2^m}$, one sees the power is a composite over two or more primes, and is thus algebraicly composite.
Thus, you just have to consider $1$ and those that come to fermat numbers.  ie $1,2, 4$.  All others are composite.
The algebraic magic is that there a divisor of $a^b-1$, for each $m\mid b$. Since $(a^b-1) (a^b+1) =a^{2b}-1$, one is then searching for any $2n$, where exactly one number divides it, but not $n$. One can write 8, etc as 2^3, and apply the same rule, and replace a by 2, and b by 3b.  This is enough to show that the only examples to work are when n is of the form $2^{2^m}$, eg m=0 gives n=2, m=1 gives n=4, m=2 gives n=16, and m=3 gives n=256.  and m=4 gives n=65536.  
Now, it is known that 16^{16}+1 has a factor, but it took many years to find it: you use the algorithm a=4,  a <= a^2-2, for a certian number of terms, until you pass n in 2^{2^n}+1, by which time, a ought come to '2'.  If this does not happen, it's composite.  In fact, there are no known fermat numbers greater than 65537, but this is not of the form $n^n+1$.
