= Sum of two squares theorem
{wiki}
= Fermat's theorem on sums of two squares
{c}
{synonym}
= Fermat's two-square theorem
{c}
{synonym}
A <positive integer> $n$ is a <sum of two squares> of <integers> exactly when every <prime factor> congruent to three <modulo> four has an even <prime exponent> in its <prime factorization>. The zero-square convention permits $1=1^2+0^2$; zero itself separately has $0=0^2+0^2$.
For necessity, let $p\equiv3\pmod4$ divide $a^2+b^2$. If $p\nmid b$, then $(ab^{-1})^2\equiv-1\pmod p$, contradicting <Euler's criterion> for minus one at such a prime. Hence $p\mid b$, and then $p\mid a$ as well. Divide both coordinates by $p$ and repeat. Each removal subtracts two from the <prime valuation> of $n$, forcing it to be even.
For sufficiency, two is $1^2+1^2$. A <prime number> congruent to one <modulo> four has a square root of minus one by <Euler's criterion>, and the <congruence lattice proof of the prime sum of two squares> turns that root into a representation of the prime. Each even power of a prime congruent to three <modulo> four is already a <perfect square>, hence a <sum of two squares> with a zero term. Finally, the <Brahmagupta-Fibonacci identity> combines the representations across all <prime powers> in $n$.
For example, $45=3^2\cdot5=6^2+3^2$ qualifies, while $21=3\cdot7$ does not. The criterion examines prime exponents, rather than only the residue of the whole number <modulo> four.
Back to article page