# 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

• 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

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

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.