Here is the question: ------------- Show that a perfect square is never of the form 3k+2 for any k. Conclude that if p is prime and [itex]p \geq 5[/itex], then [itex]p^2 + 2[/itex] is always composite. ------------- We are at the very start of the book, so there is not very much available to use. We have defined a|b, primes, floor and ceiling (which I don't think will play a role here), and have the division theorem. For the first part I think it is going to be proved by contradiction, so I have been trying to get some kind of parity going with both sides. I tried using [itex]n^2 - 1 = 3k+1[/itex] and then breaking into evens and odds, but that did not get anywhere. I was also trying to get a contradiction with [itex]3k+2 \mid n[/itex], but again was able to get nothing. Any ideas? For the second part I was using the result of the first. Since a perfect square is not of the form 3k+2 it must be of the form 3k+1 of 3k, for the former it is easy to see that [itex]p^2+2[/itex] is composite. But for the latter I am stuck again. Any ideas here? Thanks!