Motivation
Which positive integers can be written as with ? Some examples are and , whereas is not such a sum. A prime factorization gives a complete answer, but only after we explain why primes in different residue classes behave differently. Zero and negative coordinates are allowed; exchanging coordinates or changing signs does not change the sum.
The obstruction at primes congruent to three
Squares are congruent to or modulo . Thus a number congruent to modulo is not a sum of two squares. For a factorization criterion we need a stronger observation.
Theorem 7.2.1
(A prime dividing a sum of squares)
If is a prime with and , then and .
Proof
(Fermat's little theorem excludes a square root of )
Suppose instead that . Division by modulo would produce a solution . Fermat's little theorem then gives , a contradiction because is odd. Therefore , and the original congruence then gives .
Consequently, if a nonzero sum is divisible by such a prime, both coordinates can be divided by and the sum by . Repeating shows that its exponent is even. This argument does not say that every integer congruent to modulo is representable: , but both and occur to odd exponents.
Counterexample mode
The divisibility lemma needs the residue three
Claim: if a prime divides , then divides both and . This fails for : with and we have , divisible by , while and . It also fails for , since . In both cases is a square modulo ( and ), which is exactly what the proof excludes when . The repaired statement keeps that hypothesis; for the other primes the exponent of in may be odd, as shows.
Definitions
Why primes congruent to one split
We will prove that every prime is itself a sum of two squares, using the Gaussian integers and their norm.
Definition 7.2.2
(Gaussian integers and the norm)
The norm is multiplicative: , since . The units are precisely , the elements of norm .
Theorem 7.2.3
(Primes congruent to one modulo four)
Every prime is a sum of two integer squares.
Proof
(Wilson's congruence and a Gaussian factorization)
For with , round the real and imaginary parts of to nearest integers. This gives and with . Euclidean division therefore works in . Repeated division supplies a greatest common divisor and a Bézout identity, just as over the ordinary integers. In particular, an irreducible Gaussian integer is prime: if it divides but not , its gcd with is a unit, and Bézout's identity shows that it divides .
For an odd prime , pairing every nonzero residue with its inverse proves Wilson's congruence : only and are self-inverse. If , put . Pairing with gives , because is even. Hence .
Now divides in , but it divides neither factor: division by the ordinary integer would require both coefficients to be divisible by , and the imaginary coefficient is or . Thus is not a Gaussian prime and, by the Euclidean-division paragraph above (irreducible implies prime), cannot be Gaussian irreducible. Write with neither factor a unit. Multiplicativity gives ; both norms are integers greater than , so both equal . If , then . The separate prime has .
Proof X-ray
Where the residue of $p$ modulo four is used
The proof has three independent steps, and only the first uses .
- A square root of . Write . For the sign is , and Wilson's congruence gives with . For the sign is , and the same computation only gives , which carries no information; the divisibility lemma shows that has no square root modulo such a prime.
- Irreducible implies prime. Euclidean division in supplies Bézout identities, so a Gaussian irreducible that divides a product divides one of the factors. This converts “ divides but neither factor” into “ factors into two nonunits”.
- The norm counts. Multiplicativity gives with both norms greater than , so , and gives the coordinates.
The second step is not constructive: it shows that a proper factor exists without exhibiting one. The gcd computation below supplies it.
How the Gaussian division actually works
The nearest-integer step deserves a closer look because a complex quotient need not be a Gaussian integer. Write , with , and choose integers satisfying and . Put . Then
The inequality remains true at a tie, when a coordinate lies halfway between integers: either nearest integer works. The strict decrease of the nonnegative integer norm, rather than a claim that the quotient is unique, ensures termination. At the last nonzero remainder, back substitution gives a Bézout identity. A greatest common divisor is consequently determined only up to multiplication by a unit; for example and are associates and have the same norm.
Worked example 7.2.4
(Extracting a representation of 29 by division)
For , the integer satisfies . Thus divides in . To make the factorization constructive, apply the Gaussian Euclidean algorithm to and :
The quotient is obtained by rounding the two coordinates. Since
the last nonzero remainder is a gcd and gives . The second division is exact; it is not necessary to know the answer beforehand, only to carry out the divisions. By contrast, the congruence alone is not the representation: the gcd calculation converts that congruence into a factor whose norm is .
Why the gcd has norm exactly the prime
For a general prime , let be a Gaussian gcd of and , where . It is useful to see why the algorithm cannot return a unit or an associate of . If were a unit, Bézout would give . Multiplying by , both terms on the left would be divisible by , forcing , impossible because its imaginary coefficient is . If were an associate of , then , also impossible. Since , the integer divides . It is neither nor : the latter would make the complementary factor a unit and an associate of . Therefore .
This gcd argument is a constructive version of the earlier irreducibility argument. The two proofs use the same essential facts, but displaying the gcd makes clear how a congruence yields actual coordinates. Finding a square root of and carrying out the Gaussian divisions have a computational cost; the existence theorem by itself is not a complexity bound.
The complete criterion
Theorem 7.2.5
(Two-square theorem)
A positive integer is a sum of two integer squares if and only if every prime has even exponent in the prime factorization of .
Proof
(Necessity by divisibility, sufficiency by the product identity)
Necessity is the divisibility argument above. For sufficiency, write the factorization of as a product of , primes , and even powers of primes . Each individual factor is a sum of two squares: , each prime has just been proved representable, and . Finally, the identity
combines representations. It is the norm identity for . Applying it repeatedly proves sufficiency and supplies coordinates once representations of , the primes congruent to modulo , and the even-power factors have been found. The theorem concerns positive ; is an additional trivial case.
Concept lensAlgebraic
Sums of two squares as Gaussian norms
Since , the integers that are sums of two squares are exactly the norms of Gaussian integers, and the product identity is the multiplicativity of . In this language the criterion records how ordinary primes factor in . The prime equals . A prime is with , as proved above. A prime stays irreducible: a factorization into nonunits would give , so would be a sum of two squares, which is impossible modulo . Being irreducible, is a Gaussian prime, so forces or ; either way divides both coordinates of . Thus divides only through the factor , which is why its exponent is even.
Worked examples
Worked example 7.2.6
(An obstruction stronger than a congruence modulo four)
is modulo , yet the exponents of both and are odd. The criterion rules out a representation. Checking only would miss this obstruction.
Worked example 7.2.7
(Constructing a representation)
Since , combine , , and . First ; multiplying by gives . Taking norms gives . Different choices of signs and factors may yield other representations.
Worked example 7.2.8
(An even exponent need not exclude a prime)
is representable, even though divides it. Indeed . The condition is that the exponent of be even, not that be absent.
Common mistakes
Choices, signs and boundary cases
The product identity can produce more than one representation because conjugating one factor changes the product without changing its norm. For , use and . The two choices give
Their norms give . Multiplying a Gaussian factor by a unit changes signs or exchanges coordinates; conjugating changes the sign of its imaginary part. These operations explain some apparent differences, but the two pairs for are genuinely different even after ignoring signs and order. The criterion decides existence; it does not, by itself, count all representations.
There are several useful boundaries. The integer has the representation : its prime factorization has no offending exponent, so the condition is vacuously true. A negative integer cannot be a sum of two integer squares because each square is nonnegative. Neither case requires inventing a prime factorization of zero. Finally, requiring both coordinates to be positive is a different question; the theorem permits zero, so it answers the stated integer-coordinate problem rather than automatically producing two positive coordinates.
Common mistake
(A square root of does not certify a prime)
The argument for primes runs from “ is prime and ” to “ has a solution”. It cannot be reversed into a primality test: , yet is composite.
Common mistake
(Checking the residue of instead of every exponent)
A practical test starts with the complete prime factorization. For each prime congruent to modulo , check its exponent separately. A product of two such primes can be modulo while still failing the criterion, as illustrates. Conversely an even exponent can be absorbed into both coordinates: multiplying by gives . These are checks on each prime exponent, not on the total number of prime factors or merely the residue of the whole number.
Reading the exact exponent from the coordinates
The obstruction gives more information than simply an even exponent. Let be prime and suppose . Let be the largest nonnegative integer for which divides both coordinates. Such an exists, even if one coordinate is zero, because the other coordinate is nonzero. Write and ; at least one of is not divisible by . The divisibility lemma says cannot divide , for otherwise it would divide both and . Hence
This explains the evenness geometrically in terms of a common scale of the two coordinates. For example, if a nonzero sum has exactly six factors of , both coordinates are divisible by , but they cannot both be divisible by . With the convention , the statement concerns the minimum of the two coordinate valuations; it does not require the valuations themselves to be equal. For example, has one zero coordinate.
A second useful method for a small given number is a bounded search. If , then . Ignoring signs and ordering, inspect squares at most : only the pairs and sum to . Thus the two pairs already exhibited, and , are exhaustive up to those symmetries. This finite search proves completeness for this particular number, whereas the factorization criterion alone asserts only existence. For large inputs the search may be expensive, and obtaining a complete factorization can itself be difficult; neither method should be mistaken for an automatic fast algorithm.
Checking one exponent is not checking them all
Consider . The exponent of is even, and is congruent to modulo , but is congruent to modulo and occurs once. Consequently has no representation. Checking only the first prime, or combining the exponents of and into one total, would lose the information the theorem needs. In contrast, multiplying by one more factor of makes every relevant exponent even. Indeed . Here the coordinates arise by scaling by ; both happen to be positive. This both checks the criterion and exhibits a certificate that can be verified by ordinary arithmetic; a reader need not rely on the factorization argument to check the final equality.
With three squares the obstruction becomes a condition modulo eight; with four squares it disappears.
A path to generalization
Three and four squares
With three squares the obstruction becomes a condition modulo eight; with four squares it disappears.
A positive integer is a sum of three squares exactly when it is not of the form . Necessity is elementary: squares are modulo , so three of them never sum to modulo ; and if , then all three coordinates are even, since squares are or modulo . Every positive integer is a sum of four squares. The sufficiency proofs need tools beyond this note.
Exercises
Quick check
(Decide whether is a sum of two squares.)
Solution · Answer
; the exponent of is odd, so it is not.
Quick check
(Find two representations of up to signs and order.)
Solution · Answer
. These examples alone do not prove that there are no others.
Quick check
(Prove that if , then .)
Solution · Answer
, so the theorem on divisibility forces to divide both and ; their squares are divisible by .
Quick check
(Is representable?)
Solution · Answer
. The criterion agrees: , and the exponent of is even.
Quick check
(Find a representation of and explain why the factor is harmless.)
Solution · Answer
. The exponent of the prime is , so the criterion permits a representation.
Quick check
(List all representations of up to signs and order.)
Solution · Answer
If , both absolute values are at most . The only squares available are ; only sums to . Thus the sole pair up to signs and order is .
Quick check
(Suppose divides . Must divide it?)
Solution · Answer
If the sum is zero, every positive integer divides it. Otherwise its -adic exponent is even, and being at least it must be at least . Equivalently, repeatedly use the divisibility lemma on the two coordinates.
Quick check
(Find two different representations of up to signs and order.)
Solution · Answer
. These pairs are different after signs and order are ignored. The two-square theorem guarantees existence but does not claim that these are the only pairs.