There are two ways to prove it, theImPerfectHacker method by examining each case. Or ThePerfectHacker method which is more elegant. Since I am who I say I am I am going to do it my way.

You have,

a^2+b^2≡0(mod p)

Thus,

a^2≡-b^2(mod P)

Thus, the Legendre Symbol (I presume you learned them by now),

Since -b^2 is a quadradic residue of a^2 we have,

(-b^2/p)=1

Thus,

(b^2/p)(-1/p)=1

But,

(b^2/p)=1

Thus,

(-1/p)=1

That is a famous case and only happens when,

p≡1 (mod 4)

---

This looks greatly similar to Fermat's theorem about expressing 4k+1 primes as a sum of two unique squares.

The proof of that is much more complicated (I wonder how Fermat proved it )