Weird property of x^2+1=0 in modular rings

In a modular ring (the integers modulo p), there can be real (not imaginary) solutions to x^2+1=0. If p is a prime greater than two, then x^2+1=0 has two solutions if p=4n+1 (for some integer n), and zero solutions if p=4n+3.

I can prove that x^2+1=0 has solutions in pairs. (If x^2+1 = 0, mod p, then (p-x)^2+1 = p^2-2px+x^2+1 = x^2+1 = 0, mod p.)

I can even prove that x^2+1=0 has either zero or two solutions. (x and y can't both solve it for y != p-x, if p is prime, because if y=x+k, then (x+k)^2+1 = x^2+2kx+k^2+1 = 0 mod p. But x^2+1=0, so 2kx+k^2 = 0 mod p. That is, k(k+2x) = 0 mod p. But p is prime, so either k = 0 mod p, or k+2x = 0 mod p. If k = 0, then y = x (because y=x+k). If k+2x = 0 mod p, then k+2x = p, so x+(x+k) = p, so x+y=p, so y = p-x. Therefore there are never more than two solutions.)

Can anyone explain why there are always two solutions if p=4n+1, and always zero if p=4n+3?