Primes where $(p-1) ^ 2 + 1$ and $(p+1) ^ 2 + 1$ are also prime I'm following a math course about basic number theory. The course contains an Open Problems section with Landau’s conjecture, that states: "There are infinitely many primes of the form $n^2 + 1$.". Examples include:
$2 = 1^2 + 1$
$5 = 2^2 + 1$
$17 = 4^2 + 1$
$37 = 6^2 + 1$
I noticed that n in these examples are primes minus one. So I made a program that checks for the first x primes if $(p-1) ^ 2 + 1$ is also prime. This yields the primes:
$2, 3, 5, 7, 11, 17, 37, 41, 67, 127, 131, 151, 157, ..$
I also checked out $(p+1) ^ 2 + 1$, which yields:
$3, 5, 13, 19, 23, 53, 73, 83, 89, 109, 149, 179, 223, ..$
Both formula's seem to yield numbers at about the same rate.
However, what I find strange is the intersection of the sets. If I look for primes where both $(p-1) ^ 2 + 1$ and $(p+1) ^ 2 + 1$ are also prime, only 3 and 5 seem to suffice. From there the sets seem to go their seperate ways. Now I would like some insight into why this is, but I can't find the above formula's or the sets using searches. With my computer I tried the first 50 million primes but only 3 and 5 seem to have this these properties. What am I looking at here? Are there other primes known that satisfy these properties? 
 A: If $p \equiv 1$ or $2$ mod $5$, $(p+1)^2 + 1 \equiv 0 \mod 5$.  If $p \equiv 3$ or $4$ mod $5$, $(p-1)^2 + 1 \equiv 0 \mod 5$. 
A: Have you thought about comparing $(p - 1)^2 + 1$ to $(p + 1)^2 + 1$ for just a few values of $p$ and seeing what happens?


*

*$p = 2$ gives us $(p - 1)^2 + 1 = 2$ and $(p + 1)^2 + 1 = 10 = 2 \times 5$.

*$p = 3$ gives us $(p - 1)^2 + 1 = 5$ and $(p + 1)^2 + 1 = 17$.

*$p = 5$ gives us $(p - 1)^2 + 1 = 17$ and $(p + 1)^2 + 1 = 37$.

*$p = 7$ gives us $(p - 1)^2 + 1 = 37$ and $(p + 1)^2 + 1 = 65 = 5 \times 13$.

*$p = 11$ gives us $(p - 1)^2 + 1 = 101$ and $(p + 1)^2 + 1 = 145 = 5 \times 29$.

*$p = 13$ gives us $(p - 1)^2 + 1 = 145 = 5 \times 29$ and $(p + 1)^2 + 1 = 197$.

*$p = 17$ gives us $(p - 1)^2 + 1 = 257$ and $(p + 1)^2 + 1 = 325 = 5^2 \times 13$.

*$p = 19$ gives us $(p - 1)^2 + 1 = 325 = 5^2 \times 13$ and $(p + 1)^2 + 1 = 401$.


This suggests that one of $(p - 1)^2 + 1$ or $(p + 1)^2 + 1$ is prime and the other is a multiple of $5$ (though of course it's also possible both values fail to yield a prime, e.g., $p = 29$). Hopefully this enables you to make sense of Robert's tightly packed answer.
