## Is number $n^{k} + 1$ composite? [closed]

Hello, I have to find out if number $n^{k} + 1$, where $n \geq 2 \wedge k \in N$, is composite. After several google queries I got stuck. I tried to transform the problem into Fermat prime test, but the problem got only more difficult: does exist such a for which this formula is false: $(a)^{n^{k}} \equiv 1 \pmod{n^{k} + 1}$.

I would be very grateful for any advice with this exercise (just a little push towards the right way would be very nice).

-
Google queries? WHat is the world coming to... Obvious homework, voting to close. – Igor Rivin Nov 24 2011 at 22:56
Why do you have to find out if this number is composite? I don't know of any real-world problems that rely on this sort of number, and if this was needed in a proof of a theorem, I don't think you would be asking here. – David Roberts Nov 24 2011 at 23:08
I should have probably read FAQ first. Sorry for my invalid question. – Summerbreeze Nov 24 2011 at 23:08
Now, that's too difficult...it is a well known open problem whether there are infinitely many primes of the form n^2 + 1. – quid Nov 25 2011 at 0:04
Note also that Igor's initial comment refers to an earlier version of the question – Yemon Choi Nov 25 2011 at 0:27
show 3 more comments