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.
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.
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.
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!