 Sum of two squares theorem

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\equiv 3(\mathrm{mod}4)$ divide $a^2+b^2$. If $p\nmid b$, then $(a{b}^{-1}{)}^2\equiv -1(\mathrm{mod}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\cdot 5=6^2+3^2$ qualifies, while $21=3\cdot 7$ does not. The criterion examines prime exponents, rather than only the residue of the whole number modulo four.

The Sum of Two Squares Theorem states that a positive integer \( n \) can be expressed as a sum of two squares (i.e., \( n = a^2 + b^2 \) for some integers \( a \) and \( b \)) if and only if in its prime factorization, every prime of the form \( 4k + 3 \) appears with an even exponent.