Decide which integers are sums of two squares

Try

Try to write sixty-five as two squares. Both 1²+8² and 4²+7² work. By contrast, seventy-five has no representation. Searching a finite list can verify either claim for these small inputs, but prime factorization provides a criterion for every positive integer. Zero is allowed as one of the squares, so a perfect square automatically qualifies. We will prove existence, not a count of all representations.

Predict

Predict which prime factors cause trouble. Squares modulo four are zero or one, so a prime congruent to three modulo four cannot itself be a sum of two squares. That observation alone does not explain composites: nine is a sum because 9=3²+0². The correct statement is that every prime congruent to three modulo four must occur to an even exponent in the factorization of the positive integer.

Experiment

Inspect the factorization, then verify or rule out a representation.

Integer	Factorization	Criterion	Example or obstruction
25	5²	Pass	3²+4²
65	5·13	Pass	1²+8²
21	3·7	Fail	Odd exponents
49	7²	Pass	0²+7²

Do not treat the number of distinct obstructing primes as the test; each exponent matters independently.

Understand

Let q be a prime congruent to three modulo four and suppose q divides a²+b². If b were invertible modulo q, then (a/b)²=−1 would contradict the earlier criterion that−1 is a square only for odd primes congruent to one modulo four. Hence q divides b and then a. Dividing both by q removes q² from the sum; repeating proves that its valuation in a nonzero sum is even. For the converse, first prove that a prime p congruent to one modulo four is a sum. Choose r with r²=−1 modulo p and let M=floor√p. There are (M+1)²>p pairs (u, v) with 0≤u, v≤M but only p residues u+rv. Two distinct pairs agree. Their differences a, b satisfy a+rb=0 modulo p, so a²+b²=0 modulo p. They are not both zero and their squared sum is at most 2M²< 2p. The only possible positive multiple is therefore p.

Apply

The product identity (a²+b²)(c²+d²)=(ac−bd)²+(ad+bc)² now assembles the general representation. The prime two is 1²+1²; each prime congruent to one modulo four has the representation just proved; an even power q^(2k) is (q^k)²+0². Multiplying these factors proves sufficiency. For a concrete construction use 5=1²+2² and 13=2²+3². The identity gives 65=(2−6)²+(3+4)²=4²+7². Changing signs in the input representations can produce a different output, which explains why the theorem does not promise uniqueness.

Continue

Given a new positive integer, factor it and write a certificate: either an obstructing prime with odd exponent or an explicit pair of squares. Factoring large integers can be computationally difficult even though the theorem is concise. The pigeonhole proof establishes existence for a prime but is not automatically the fastest search algorithm. More efficient constructions use modular square roots and Euclidean methods. Keep these three claims separate: a classification theorem, a constructive proof, and an efficient implementation.

Return to the number theory unit to choose a targeted retry. Continue with turn a hypothetical solution into a smaller one.