Let $p$ be a prime so $p\equiv3\pmod4$. If $p|a^2+b^2$, then $p|a,b$

The ring $ \mathbf Z[i] $ is a principal ideal domain, and any prime that is 3 modulo 4 is inert in this ring. Indeed, writing $ p = (a+bi)(a-bi) = a^2 + b^2 $ and looking at this modulo 4, we find that $ p $ cannot be $ 3 $ modulo $ 4 $. Now, assume that $ p $ divides $ a^2 + b^2 = (a+bi)(a-bi) $, then $ p $ divides one of the factors on the right hand side. Hence, $ p $ divides both $ a $ and $ b $.

Another approach: if we have $ a^2 + b^2 \equiv 0 \pmod{p} $ with $ a, b \neq 0 $, then $ (a/b)^2 \equiv -1 \pmod{p} $, so $ a/b $ has order $ 4 $ in the group $ (\mathbf Z/p \mathbf Z)^{\times} $, which has order $ p - 1 $. This is not divisible by $ 4 $ as $ p \equiv 3 \pmod{4} $, contradicting Lagrange's theorem.

I hope I didn't miss something and I think it is pretty elementar:

Using Fermats Little Theorem: $a^p\equiv a\mod{(p)}$ and $b^p\equiv b\mod{(p)}$. Now we get that $a^{p+1}+b^{p+1}\equiv a^2+b^2 \equiv 0 \mod{(p)}$. Because $4\mid p+1$ we can write $p+1=4k$ , for some $k\in\mathbb{N}$. Now we get: $0\equiv a^{4k}+b^{4k}\equiv a^{4k}+(-a^2)^{2k}\equiv a^{4k}+a^{4k}\equiv 2a^{4k} \mod{(p)}$. So now that means $p$ divides $2a^{4k}$, but bcs $p>2$ it cant divide the 2 so it has to divide $a^{4k}$, and if it is a factor of it, it has to be also a factor of $a$, in other words $p\mid a\Rightarrow p\mid b$.