Best stated as:
A prime number p is the sum of two squares iff p + 1 is not a multiple of 4.
We'll come to a proof of that in a moment. First, let's look at an implication for this result, so I can retain the interest of those of you not concerned with the proof.
We know that a prime number is either Gaussian prime or it is the sum of two squares. Now we have an incredibly quick way to check if a number is the sum of two squares, given that it is prime, based on the following simple logic. If p is a Gaussian prime,
p + 1 = 0 [mod 4]
p = 3 [mod 4]
So to determine if a prime is also Gaussian prime, we simply find it's remainder after division by four. If we get three, it is certainly Gaussian prime. If not, it certainly isn't.
That's just one application. I'm sure there's many more; indeed, let me know if you can think of something fairly straight-forward.
Now for a proof. It's not so tricky. I'm going to lift this example straight from a popular book, if you'll forgive me. It keeps things simple. Given that 13 is a prime, we'll show that it isn't Gaussian prime.
From Wilson's primality test, which has no practical applications but is handy for this proof, we know that 13 is a factor of:
12! + 1 = 1 x 2 x 3 ... x 12 + 1
Now, let's look at the same expression, modulo 13. Clearly 7 = -6 mod 13, and we can apply similar logic to all the second half of the expression:
1 x 2 x 3 x 4 x 5 x 6 x (-6) x (-5) x (-4) x (-3) x (-2) x (-1) + 1.
Now we can pair the m and -m terms off nicely, and write as another factorial: (6!)² + 1, in fact. A little more manipulation:
(6!)² + 1
= (6!)² - i² Now by difference of squares:
= (6! + i)(6! - i)
Bear in mind that all this time we're still dealing with the original number 12! + 1, which was a multiple of 13. So 13 can't be Gaussian prime, because it divides (6! + i)(6! - i) while not dividing either of that number's factors.
From this example, the generalisation is fairly easy to see. When p + 1 is not a multiple of 4, the above pairing of m and -m fails, and we have no complex factors. Since we know (see Gaussian prime if you didn't) that the complex factors of a prime, if they exist, are (a + bi)(a - bi), which is a² + b², it is apparent that the lack of complex factors also indicates that p cannot be made by summing two squares, and vice versa. QED.