This question concerns a proof from the book 'Proofs from the Book' Sixth Edition by M. Aigner and G. Ziegler.
The theorem and proof in question are on page 21 of my copy.
Theorem: Every prime of the form $p = 4m + 1$ is a sum of two squares, i.e. can be written $p = x^2+y^2$ for some $x,y \in Z$
There are apparently many proofs to this but the proof I am looking at is where for any s we construct two non-identical $(x',y')$ and $(x'',y'')$ with both in $ \{0,1,...\lfloor \sqrt p \rfloor \} $ where $ x' - sy' \equiv x'' - sy'' $ (mod p).
Then as you can show $\exists$s such that $s^2 \equiv -1$ (mod p) you take some differences, do some squares and bada boom you have $x^2 + y^2 \equiv 0$ (mod p) and because both x and y are $< \sqrt p$ $x^2 + y^2 < 2p \implies x^2 + y^2 = p$
I realize somewhere in my 'broad strokes must be what I'm missing but I cannot see it and I cannot really reproduce the whole proof. It was credited to Axel Thue FYI.
What I want to know is, this proof seems to apply to all p but the theorem statement goes out of the way to restrict it to p of the form $p=4m+1$.
Indeed it is pretty trivial to prove independently that the above relationship does not hold for $p=4m+3$ which is pretty much all the other primes (except $p=2$).
But where in my proof do I break down if $p=4m+3$?
Thanks in advance for helping fill a gap for me. I really like this proof but this is a gap for me.
You needed to find an $s$ such that $ s^ 2 \equiv -1 \pmod{p}$.
There is no such $s$ when $ p = 4k + 3$. (Can you show why?)
When $ p = 4k+1$, you can find such an $s$ by using $(p-1)! \equiv -1 \pmod{p}$.