If $p\geq 5$ is a prime number, show that $p^2+2$ is composite. Problem: If $p\geq 5$ is a prime number, show that $p^2+2$ is composite.
Remarks: Now if one observes that $p$ takes the forms $6k+1$ and $6k+5$, the problem is resolved quite easily. However, if one were to choose other forms say $4k+1$ and $4k+3$ then $p^2$ would be of the form $4p+1$ which would yeild the general form $4p+3$ on addition with $2$. Obviously this does not lead to any concrete conclusion. I was wondering whether there is any specific procedure involved in finding the right quotients (For eg. $6$ and $4$) or is this just a random problem solving trick. Moreover, if anyone could provide some intuition as to why $6$ works would be much appreciated. 
 A: If $p$ is a prime larger than $3$, then $p \equiv 1$ mod $3$ or $p \equiv 2$ mod $3$, hence in either case $p^2 + 2 \equiv 0$ mod $3$. Meaning $3$ divides $p^2 +2$. $p^2 + 2$ cannot be equal to $3$, so it must indeed be composite.
A: I suppose the reason is that $p^2 + 2$ is always divisible by 3; hence, taking a quotient by any multiple of 3 will allow you to prove the result. On the other hand, the number $p^2 + 2$ will never be divisible by 2, so you should not expect taking the numbers mod 4 to give you any information.
A: So it is in fact quite simple!
p is a prime number, and it is not 2 and it is not 5. We also know it is not even (if it were, then it would be 2 or it would not be prime since 2 would divide it). 
If we divide p by 6, then the remainder must be 1 or 5.
    If it were 0, then it would be a multiple of 6 --> even ---> not prime
    If it were 2, then it would be even ---> not prime
    If it were 3, then since 3 divides 6, it would be a multiple of 3--->not prime 
    If it were 4, then it would be even --> not prime
So that leaves 1 and 5. 
So you have two cases. p=5k+1 or p=5k+5.
I hope this helps! 
A: Firstly, $p$ must be odd. Let's see some examples:
$p=5 \Rightarrow p^2 +2=27=3\cdot9$, 
$p=7 \Rightarrow p^2 +2=51=3\cdot17$,
$p=11 \Rightarrow p^2 +2=123=3\cdot41$,
This suggests that $p^2 +2$ is a multiple of 3. Let $p$ be the form $6k+1$, with $k$ integer. Then we have
$$
(6k+1)^2 +2=36k^2+12k+1+2=3(12k^2+4k+1)
$$
Therefore, $p^2 +2$ is composite. 
