# Sum of two squares $n = a^2 + b^2$ [duplicate]

Is there any elementary proof for this theorem: A number $n$ is a sum of two squares if and only if all prime factors of of the form $4k+3$ have even exponent in the prime factorization of $n$.

## marked as duplicate by draks ..., Gerry Myerson, Grigory M, Per Manne, rschwiebNov 28 '12 at 14:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• As far as I remember, this wasn't that easy, needing the quadratic residue theorem and Euklid's identity (I hope it's called this way). – yo' Nov 28 '12 at 12:04

## 2 Answers

Well, it isn't that easy nor that straightforward. You need the following step (and I'm not saying this is the only way to prove, but I think is the most straightforward):

1) A prime $\,p\,$ is expressable as the sum of two (integer, all the time) squares iff $\,p=1\pmod 4\,$

2) The product of two sums of squares is again a sum of squares

3) Your claim.

For the above ne needs, imo, at least some basic group theory and some basic number theory. You check whether you know some of these.

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma.

Further, primes of the form $p=4n+3$, never have a decomposition into $2$ squares, proven in various ways here.

• The link of Thue's Lemma is broken. – MonsieurGalois Dec 30 '16 at 2:37