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.

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

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .