$p = x^2 + y^2$ where does proof limit cases it applies

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.

• @calvin, indeed I did define that in the question, we only need to constrain that towards the end, all prior applies for all s Apr 18, 2020 at 22:32
• So sorry, you're correct! Thanks Apr 18, 2020 at 22:38

1 Answer

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}$$.