@oscarmetalbreak Primes not of the form 4k+3 can always be written as the sum of two squares. And that is related to the fact that $x^2+1\equiv 0 \pmod p$ always has a solution for such primes. See
en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares