Sum of two squares Created 2026-10-20 Updated 2026-11-05
A sum of two squares representation of a nonnegative integer is an equality with integers . For example, has two representations even before changing signs or interchanging the two terms.
Counting conventions matter. If ordered pairs and signs are distinguished, the representation generates eight pairs, whereas generates only four and only one. Every perfect square is zero or one modulo four, so an integer congruent to three modulo four is impossible. That quick obstruction is insufficient by itself: also has no representation. The exact prime factorization criterion is the sum of two squares theorem.
Sum of two squares theorem Created 2026-09-24 Updated 2026-11-05
A positive integer 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 ; zero itself separately has .
For necessity, let divide . If , then , contradicting Euler's criterion for minus one at such a prime. Hence , and then as well. Divide both coordinates by and repeat. Each removal subtracts two from the prime valuation of , forcing it to be even.
For sufficiency, two is . 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 .
For example, qualifies, while does not. The criterion examines prime exponents, rather than only the residue of the whole number modulo four.