On the primality of integers of the form $p^2+k$

I am not able to find an answer to the following question:

For which positive even integers $k$ is the integer $$p^2+k$$ prime, where $p$ is a prime number $\gt5$?

• In other words, we should desscribe the set $S:=\{q-p^2\mid q,p\text{ prime}, q>p^2, p>5\}$. As $q\equiv \pm1\pmod 6$ and $p^2\equiv 1\pmod 6$, clearly $k\in S$ implies $k\equiv 0$ or $\equiv 4\pmod 6$. – Hagen von Eitzen May 13 '13 at 9:21
• @Hagen von Eitzen: Is it another way to put the equation in $n$? If the answer is yes...yes – Riccardo.Alestra May 13 '13 at 9:25

$p^2 \equiv 1(\mod 3)$
$p^2+ k \not \equiv 0(\mod 3) \implies k$ is of form $3n$ or $3n+1$.
$p^2 \equiv 1(\mod 2) \implies k \equiv 0( \mod 2)$ (since it is the stronger condition)
You can get $k$ in $(\mod 6)$,using CRT.
Similarily, you have $p^2 \equiv \pm 1\mod 5 \implies k \equiv 2,3$ or $0(\mod 5)$ . You can use CRT again to get $k \equiv x(\mod 30)$, you get a stronger condition.
Note that $\gcd(3,4) •$2$or$0\pmod 4$is not better than$0\pmod 2$, so this is just the necessary condition from my comment above. A sufficient condition would be nice. – Hagen von Eitzen May 13 '13 at 10:10 • In that case, after considering$(\mod 6) $,we can have$p$in ($\mod 5)\$, and find out a stronger condition. – Inceptio May 13 '13 at 10:16