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?
 A: As you noted, we only have to check even $n\gt 2$. Note that $16^{16}$ is (barely) too big to be considered.
So we are only worried about $4, 6,\dots, 14$.
Let $n=km$ where $k$ is odd and $\gt 1$. Then $n^n+1=(n^m)^k+1$. This is divisible by $n^m+1$. 
We have therefore eliminated all the even numbers in our range except $4$ and $8$. Your turn! 
A: 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$.
A: How can you factorize $x^k+1$? Well you can do that if $k$ is odd.
So we can factorize $n^n+1$ if $n$ has an odd prime factor, in other words if $n$ is not a power of $2$.
More precisely, if $n=dk$ with $k>1$ odd we see that $n^n+1=(n^d)^k+1$ is divisible by $n^d+1$ and hence not a prime.
So we are left to check the cases where $n=2^k$.
If $n=1,2$ you already checked.
If $n=4$ we have $4^4+1=257$ is a prime.
If $n=8$ we have $8^8+1=2^{24}+1$ is divisible by $2^8+1$ as above.
And then one checks that $16^{16}+1$ is already larger than $10^{19}$.
One way to see this is to note that
$16^{16}=2^{64}=16 \cdot 1024^6>10 \cdot 1000^6=10^{19}.$
