Sums of two squares
Some whole numbers are the sum of two perfect squares and others are not. Which ones are, and how can we find the two squares without trying every pair?
Where you are 5 in Quadratic residues and beyond
Why this exists
A point (x, y) with integer coordinates lies at distance \displaystyle \sqrt{n} from the origin exactly when x^2 + y^2 = n. So asking which circles centered at the origin pass through lattice points is asking which integers are sums of two squares: 5, 8, 9, 10, 13 are, 3, 6, 7, 11, 12 are not.
Fermat stated in 1640, without a published proof, that every prime 4k + 1 is a sum of two squares; Euler published the first proof over a century later. This lesson proves it with a square root of -1 (Quadratic residues and the Legendre symbol) and the pigeonhole principle, then decides every positive integer from its factorization (Every number has exactly one prime factorization).
Definition
An integer n is a sum of two squares if n = x^2 + y^2 for some integers x and y. Zero is allowed, so 9 = 3^2 + 0^2 is a sum of two squares. Each ordered pair (x, y) with x^2 + y^2 = n is a representation of n, and
counts them, signs and order included: 5 = 1^2 + 2^2 has the eight representations (\pm 1, \pm 2) and (\pm 2, \pm 1), so r_2(5) = 8. A representation is primitive if \gcd(x, y) = 1.
For a prime q and a positive integer n, v_q(n) is the exponent of q in the prime factorization of n; so v_q(n) = 0 when q \nmid n.
Intuition
From 65 = 1 + 64 = 16 + 49, the circle x^2 + y^2 = 65 passes through the 16 lattice points (\pm 1, \pm 8), (\pm 8, \pm 1), (\pm 4, \pm 7) and (\pm 7, \pm 4).
Why two essentially different pairs? Write 5 = |2 + i|^2 and 13 = |3 + 2i|^2 with Complex numbers. The modulus is multiplicative (Modulus, argument and polar form), so 65 is the squared modulus of (2 + i)(3 + 2i) = 4 + 7i, and also of (2 + i)(3 - 2i) = 8 - i. This product rule builds sums of two squares out of primes; the other half is which primes are sums of two squares. If p = x^2 + y^2 with p an odd prime, then p \nmid y (otherwise p divides x too, and p^2 divides p), and dividing by y^2 modulo p gives (x y^{-1})^2 \equiv -1. So -1 must be a square modulo p, which by Quadratic residues and the Legendre symbol forces p \equiv 1 \pmod 4. For the converse, a pigeonhole argument shrinks a square root of -1 modulo p to two numbers below \displaystyle \sqrt{p} whose squares add up to exactly p.
Results
Throughout, p denotes a prime.
Theorem 1 (squares modulo 4). Every square is \equiv 0 or 1 \pmod 4. So no integer n \equiv 3 \pmod 4 is a sum of two squares.
Theorem 2 (the product identity). For all integers a, b, c, d,
Equivalently, |z|^2 |w|^2 = |zw|^2 for z = a + bi and w = c + di. A product of sums of two squares is a sum of two squares.
Theorem 3 (Thue’s lemma). Let p be a prime and a an integer with p \nmid a. There are integers x and y with
and x may be taken with \displaystyle 1 \le x \le \lfloor \sqrt{p} \rfloor.
Theorem 4 (Fermat’s two-squares theorem). An odd prime p is a sum of two squares if and only if p \equiv 1 \pmod 4. Also 2 = 1^2 + 1^2.
Theorem 5 (comparing two representations). Let n = a^2 + b^2 = c^2 + d^2 with a, b, c, d positive integers. Then
and ac + bd \le n with equality only if (c, d) = (a, b), and ad + bc \le n with equality only if (c, d) = (b, a). In particular a prime p has at most one representation p = a^2 + b^2 with a > b > 0, and r_2(p) = 8 for every prime p \equiv 1 \pmod 4.
Lemma. Let q \equiv 3 \pmod 4 be a prime. If q \mid x^2 + y^2, then q \mid x and q \mid y.
Theorem 6 (which integers). A positive integer n is a sum of two squares if and only if v_q(n) is even for every prime q \equiv 3 \pmod 4.
Theorem 7 (the number of representations; stated without proof). Write a positive integer as n = 2^{f} \prod p^{a_p} \prod q^{b_q}, the first product over primes p \equiv 1 \pmod 4 and the second over primes q \equiv 3 \pmod 4. Then
Equivalently, r_2(n) = 4\bigl(d_1(n) - d_3(n)\bigr), where d_1(n) and d_3(n) count the positive divisors of n that are \equiv 1 and \equiv 3 \pmod 4. The proof uses unique factorization in the Gaussian integers \mathbb{Z}[i] (Euclidean domains and principal ideal domains) and is in standard texts such as Hardy and Wright, An Introduction to the Theory of Numbers. Here only the case n = p (Theorem 5) and the zero case (Theorem 6) are proved.
Why it is true
Theorem 1. An even square is (2t)^2 = 4t^2 \equiv 0 and an odd square is (2t + 1)^2 = 4t(t + 1) + 1 \equiv 1 \pmod 4. A sum of two of them is \equiv 0, 1 or 2.
Theorem 2. Expand both sides: each equals a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2, the cross terms \mp 2abcd cancelling. In complex form, zw = (ac - bd) + (ad + bc)i and |zw| = |z||w|; the second line is the same computation with w replaced by \bar{w} = c - di.
Theorem 3. Let \displaystyle k = \lfloor \sqrt{p} \rfloor. A prime is not a perfect square, so \displaystyle k < \sqrt{p} and (k + 1)^2 > p. Consider the (k + 1)^2 pairs (u, v) with 0 \le u, v \le k and the remainders of au - v modulo p. There are more pairs than remainders, so by the pigeonhole principle (The pigeonhole principle) two different pairs (u_1, v_1) and (u_2, v_2) give the same remainder. Put x = u_1 - u_2 and y = v_1 - v_2. Then ax \equiv y \pmod p, \displaystyle |x|, |y| \le k < \sqrt{p}, and (x, y) \ne (0, 0). If x = 0, then p \mid y with |y| < p, so y = 0, impossible. If y = 0, then p \mid ax with p \nmid a, so p \mid x by Euclid’s lemma (Bezout's identity and the extended Euclidean algorithm) and x = 0, impossible. Replacing (x, y) by (-x, -y) if needed makes x positive. \square
Theorem 4. If p \equiv 3 \pmod 4, Theorem 1 rules it out. Let p \equiv 1 \pmod 4. By Theorem 5 of Quadratic residues and the Legendre symbol, \displaystyle \left(\frac{-1}{p}\right) = 1, so some integer r has r^2 \equiv -1 \pmod p, and p \nmid r. Theorem 3 with a = r gives x, y with rx \equiv y and \displaystyle 0 < |x|, |y| < \sqrt{p}. Then
while 0 < x^2 + y^2 < p + p = 2p. The only multiple of p strictly between 0 and 2p is p, so x^2 + y^2 = p. \square
Theorem 5. Multiplying out,
By Theorem 2, (ac + bd)^2 + (ad - bc)^2 = n^2, so ac + bd \le n, with equality only if ad = bc. In that case a/b = c/d, so (c, d) = \lambda(a, b) with \lambda = c/a > 0, and c^2 + d^2 = \lambda^2 n = n forces \lambda = 1. In the same way (ad + bc)^2 + (ac - bd)^2 = n^2 gives ad + bc \le n, with equality only if ac = bd, which forces (c, d) = (b, a).
Now let n = p be prime with two such representations. Then p divides (ac + bd)(ad + bc), so by Euclid’s lemma it divides one factor. That factor is positive and at most p, so it equals p, and then (c, d) = (a, b) or (b, a). For p \equiv 1 \pmod 4 a representation exists by Theorem 4, with a \ne b (else p = 2a^2 is even) and b \ne 0 (p is not a square). Every representation then has \{|x|, |y|\} = \{a, b\}, and the eight sign and order choices (\pm a, \pm b), (\pm b, \pm a) are distinct, so r_2(p) = 8. \square
Lemma. Suppose q \nmid y. Then y has an inverse modulo q (Modular inverses and linear congruences); put t \equiv x y^{-1}. From x^2 \equiv -y^2 we get t^2 \equiv -1 \pmod q, so \displaystyle \left(\frac{-1}{q}\right) = 1, contradicting Theorem 5 of Quadratic residues and the Legendre symbol since q \equiv 3 \pmod 4. So q \mid y, then q \mid x^2, and q \mid x by Euclid’s lemma. \square
Theorem 6. If. Each prime power in n is a sum of two squares: 2 = 1^2 + 1^2, a prime p \equiv 1 \pmod 4 by Theorem 4, and q^{2b} = (q^b)^2 + 0^2. Also 1 = 1^2 + 0^2. By Theorem 2 and induction on the number of prime factors, so is their product n.
Only if. Fix a prime q \equiv 3 \pmod 4. We prove by Strong induction and well-ordering on e that every positive sum of two squares n with v_q(n) = e has e even. For e = 0 this holds. Let e \ge 1 and n = x^2 + y^2. Since q \mid n, the Lemma gives x = qx' and y = qy', so q^2 \mid n, which means e \ge 2, and n/q^2 = x'^2 + y'^2 is a positive sum of two squares with v_q(n/q^2) = e - 2. By the induction hypothesis e - 2 is even, so e is even. \square
Worked examples
Deciding from the factorization
Decide whether 245, 1386 and 1300 are sums of two squares, and give a representation of each one that is.
SolutionFactor each: 245 = 5 \cdot 7^2, 1386 = 2 \cdot 3^2 \cdot 7 \cdot 11 and 1300 = 2^2 \cdot 5^2 \cdot 13. The primes \equiv 3 \pmod 4 are 7 in the first, 3, 7, 11 in the second, and none in the third.
In 245 the exponent of 7 is 2, even, so 245 is a sum of two squares by Theorem 6. The proof of Theorem 6 says how: 245 = 7^2(2^2 + 1^2) = 14^2 + 7^2.
In 1386 the exponent of 7 is 1 (so is that of 11), so 1386 is not a sum of two squares.
For 1300 there is nothing to check: 1300 = 10^2(3^2 + 2^2) = 30^2 + 20^2.
A prime through Thue’s lemma
Write 181 as a sum of two squares by following the proof of Theorem 4.
SolutionFirst we need a square root of -1 modulo the prime 181 = 4 \cdot 45 + 1. As 181 \equiv 5 \pmod 8, the number 2 is a nonresidue (Theorem 8 of Quadratic residues and the Legendre symbol), so Euler’s criterion gives 2^{90} \equiv -1, and r = 2^{45} has r^2 \equiv -1. By repeated squaring (Powers modulo n), 2^8 = 256 \equiv 75, 2^{16} \equiv 75^2 = 5625 \equiv 14, 2^{32} \equiv 14^2 = 196 \equiv 15, and 45 = 32 + 8 + 4 + 1, so
Check: 162^2 = 26{,}244 = 145 \cdot 181 - 1. So r = 162.
Now \displaystyle \lfloor \sqrt{181} \rfloor = 13, and Theorem 3 promises an x with 1 \le x \le 13 for which the remainder y of 162x, taken between -90 and 90, has \displaystyle |y| < \sqrt{181} \approx 13.45. For x = 1, \dots, 9 the values of y are -19, -38, -57, -76, 86, 67, 48, 29, 10. At x = 9, 162 \cdot 9 = 1458 = 8 \cdot 181 + 10, so y = 10. The proof of Theorem 4 now gives 181 = 9^2 + 10^2, and indeed 81 + 100 = 181.
Every representation of a product of three primes
Find every way to write 1885 = 5 \cdot 13 \cdot 29 as x^2 + y^2 with x > y > 0.
SolutionEach prime is \equiv 1 \pmod 4: 5 = |2 + i|^2, 13 = |3 + 2i|^2 and 29 = |5 + 2i|^2. Multiply, choosing each factor or its conjugate; conjugating the whole product changes only signs, so the first factor can stay fixed: (2 + i)(3 + 2i) = 4 + 7i and (2 + i)(3 - 2i) = 8 - i, then
By Theorem 2 each modulus squared is 1885, so
Are there more? By Theorem 7, r_2(1885) = 4 \cdot 2 \cdot 2 \cdot 2 = 32. Each pair above with x > y > 0 accounts for eight representations (signs and order), and 4 \cdot 8 = 32, so these four are all of them.
Holes on a pegboard hoop
Hiro is building a game on a large pegboard whose holes sit at the points with integer coordinates, one unit apart. He centers a circular wire hoop of radius 25 units on a hole. How many holes lie exactly under the wire? Yuna suggests radius 26 instead; how many then?
SolutionA hole (x, y) is under the wire when x^2 + y^2 = 625, so the count is r_2(625). Since 625 = 5^4 with 5 \equiv 1 \pmod 4, Theorem 7 gives r_2(625) = 4(4 + 1) = 20. A search finds 625 = 25^2 + 0^2 = 24^2 + 7^2 = 20^2 + 15^2: the pair (25, 0) gives four points (\pm 25, 0), (0, \pm 25), and each other pair gives eight, for 4 + 8 + 8 = 20 holes.
For radius 26, 676 = 2^2 \cdot 13^2, so r_2(676) = 4(2 + 1) = 12: 676 = 26^2 + 0^2 = 24^2 + 10^2, giving 4 + 8 = 12 holes. The larger hoop passes over fewer holes: the count depends on how the squared radius factors.
A proof: rational squares give integer squares
Prove that a positive integer is a sum of two squares of rational numbers only if it is a sum of two squares of integers. Deduce that the circle x^2 + y^2 = 3 has no point with rational coordinates.
SolutionLet n = s^2 + t^2 with s, t rational, and write s = a/c, t = b/c with a common denominator c \ge 1. Then nc^2 = a^2 + b^2 is a positive sum of two integer squares. Let q \equiv 3 \pmod 4 be prime. By Theorem 6, v_q(nc^2) = v_q(n) + 2v_q(c) is even, so v_q(n) is even. This holds for every such q, so Theorem 6 makes n a sum of two integer squares. \square
By Theorem 1, 3 is not a sum of two integer squares, so not of two rational squares either: the circle x^2 + y^2 = 3 misses every rational point, while x^2 + y^2 = 2 passes through (1, 1).
Two representations reveal a factor
Use 2501 = 50^2 + 1^2 = 49^2 + 10^2 to factor 2501.
SolutionTake (a, b) = (50, 1) and (c, d) = (49, 10). Theorem 5 says 2501 divides (ac + bd)(ad + bc), where
The two representations are different, so by Theorem 5 both factors lie strictly between 0 and 2501, and 2501 divides neither. Then g = \gcd(2501, 2460) is a proper factor: g < 2501 because 2501 \nmid 2460, and g > 1 because if \gcd(2501, 2460) = 1, the coprime factor lemma (Bezout's identity and the extended Euclidean algorithm) would make 2501 divide 549. The The Euclidean algorithm and coprime numbers gives 2501 - 2460 = 41 and 2460 = 60 \cdot 41, so g = 41, and 2501 = 41 \cdot 61. The other factor agrees: \gcd(2501, 549) = 61.
Boundaries
Theorem 4 is about primes. A composite n \equiv 1 \pmod 4 need not be a sum of two squares: 21 = 3 \cdot 7 is not, because the exponents of 3 and 7 are odd. For composites the test is Theorem 6, which looks at the factorization, not at n \bmod 4. Zero counts as a square here: 9 = 3^2 + 0^2, though 9 is not a sum of two positive squares.
With more squares the rule changes. No integer 8m + 7 is a sum of three squares (Exercise 16); the three-square theorem of Legendre and Gauss says a positive integer is a sum of three squares exactly when it is not of the form 4^a(8m + 7), and Lagrange proved that every positive integer is a sum of four squares. Both are stated here without proof. Other forms need other rules: a prime p is x^2 + 2y^2 exactly when p = 2 or p \equiv 1, 3 \pmod 8.
Where this goes next
In the Gaussian integers a prime p \equiv 1 \pmod 4 splits as (a + bi)(a - bi), a prime q \equiv 3 \pmod 4 stays prime, and Theorem 7 follows from unique factorization (Euclidean domains and principal ideal domains, Unique factorization domains, Prime and maximal ideals). The hypotenuse of a primitive Pythagorean triple is odd and a sum of two squares of coprime integers, so by Exercise 12 its prime factors are all \equiv 1 \pmod 4; Exercise 15 shows each such prime is a hypotenuse (Pythagorean triples and Fermat's last theorem for n = 4). Pell's equation and continued fractions studies x^2 - dy^2 = 1, where the minus sign allows infinitely many solutions.
Exercises
Deciding and constructing
- Decide whether each of 333, 2024, 441 and 3185 is a sum of two squares, and give a representation of each one that is.
- Write 149 and 233 as sums of two squares.
- Let p = 157. Compute r = 2^{39} \bmod 157, check that r^2 \equiv -1 \pmod{157}, and use the method of Example 2 to write 157 as a sum of two squares.
- Given 397 = 19^2 + 6^2, find an integer r with r^2 \equiv -1 \pmod{397}.
- Use Theorem 2 with 13 = 3^2 + 2^2 and 37 = 6^2 + 1^2 to write 481 as a sum of two squares in two different ways.
- Find r_2(1000), r_2(1225) and r_2(1323).
- List every representation 1000 = x^2 + y^2 with x > y > 0.
- Given 1961 = 44^2 + 5^2 = 40^2 + 19^2, factor 1961 by the method of Example 6.
- On Hiro’s pegboard, what is the smallest positive integer n for which the circle x^2 + y^2 = n passes through exactly 24 holes?
- How many points with integer coordinates lie on the circle x^2 + y^2 = 2023? On x^2 + y^2 = 2025?
Proofs
- Prove that x^2 + y^2 = 7z^2 has no integer solution other than x = y = z = 0.
- Prove that if a positive integer n has a primitive representation, then 4 \nmid n and no prime q \equiv 3 \pmod 4 divides n.
- Prove that r_2(2n) = r_2(n) for every positive integer n.
- Prove that 4 \mid r_2(n) for every positive integer n, and that 8 \mid r_2(n) when n is neither a square nor twice a square.
- Let p \equiv 1 \pmod 4 be prime. Prove that p^2 = c^2 + d^2 for some positive integers c and d. Then prove that for a prime q \equiv 3 \pmod 4, every representation of q^2 has x = 0 or y = 0.
- Prove that no integer of the form 8m + 7 is a sum of three squares.
- Prove that there are infinitely many positive integers n such that n, n + 1 and n + 2 are all sums of two squares.
Answers
- 333 = 18^2 + 3^2; 2024 is not; 441 = 21^2 + 0^2; 3185 = 56^2 + 7^2. Here 333 = 3^2(6^2 + 1^2), 2024 = 2^3 \cdot 11 \cdot 23 has 11 to an odd power, 441 = 3^2 \cdot 7^2, and 3185 = 7^2 \cdot 65 = 7^2(8^2 + 1^2).
- 149 = 10^2 + 7^2 and 233 = 13^2 + 8^2, found by trying x up to \displaystyle \sqrt{p}.
- r = 129 and 157 = 11^2 + 6^2. As 157 \equiv 5 \pmod 8, 2 is a nonresidue. Repeated squaring gives 2^8 \equiv 99, 2^{16} \equiv 67, 2^{32} \equiv 93, so 2^{39} \equiv 93 \cdot 2^7 = 11{,}904 \equiv 129, and 129^2 = 16{,}641 = 106 \cdot 157 - 1. The remainders of 129x for x = 1, \dots, 6 are -28, -56, 73, 45, 17, -11, and \displaystyle |-11| < \sqrt{157}, so 157 = 6^2 + 11^2.
- r = 334 (or 63 = 397 - 334). From 19^2 \equiv -6^2, r = 19 \cdot 6^{-1} works: 6 \cdot 331 = 1986 = 5 \cdot 397 + 1, so 6^{-1} \equiv 331 and 19 \cdot 331 = 6289 \equiv 334. Check: 63^2 = 3969 = 10 \cdot 397 - 1.
- 481 = 16^2 + 15^2 = 20^2 + 9^2. With (a, b, c, d) = (3, 2, 6, 1): ac - bd = 16, ad + bc = 15, ac + bd = 20, ad - bc = -9.
- r_2(1000) = 16, r_2(1225) = 12, r_2(1323) = 0. By Theorem 7: 1000 = 2^3 \cdot 5^3 gives 4 \cdot 4; 1225 = 5^2 \cdot 7^2 gives 4 \cdot 3; 1323 = 3^3 \cdot 7^2 has 3 to an odd power.
- 1000 = 30^2 + 10^2 = 26^2 + 18^2. These give 2 \cdot 8 = 16 = r_2(1000) representations, so there are no others.
- 1961 = 53 \cdot 37. With (a, b, c, d) = (44, 5, 40, 19), ac + bd = 1760 + 95 = 1855 and \gcd(1961, 1855) = \gcd(1855, 106), which is \gcd(106, 53) = 53; also ad + bc = 836 + 200 = 1036 and \gcd(1961, 1036) = 37.
- n = 325. Theorem 7 needs \prod (a_p + 1) = 6, so the part of n built from primes p \equiv 1 \pmod 4 is p^5 or p^2 p', smallest 5^5 = 3125, 5^2 \cdot 13 = 325, 5 \cdot 13^2 = 845; factors 2 or q^2 only make n larger. Check: 325 = 18^2 + 1^2 = 17^2 + 6^2, and 325 = 15^2 + 10^2.
- None on the first, 12 on the second. 2023 = 7 \cdot 17^2, and 2025 = 3^4 \cdot 5^2 gives 4 \cdot 3: (\pm 45, 0), (0, \pm 45), (\pm 36, \pm 27), (\pm 27, \pm 36).
- Proof. Suppose z \ne 0. Then n = 7z^2 is a positive sum of two squares with v_7(n) = 1 + 2v_7(z) odd, which Theorem 6 forbids. So z = 0, then x^2 + y^2 = 0 forces x = y = 0. \square
- Proof. Let n = x^2 + y^2 with \gcd(x, y) = 1. If a prime q \equiv 3 \pmod 4 divided n, the Lemma would give q \mid x and q \mid y, contradicting \gcd(x, y) = 1. If 4 \mid n, then x^2 + y^2 \equiv 0 \pmod 4; squares are \equiv 0 or 1 (Theorem 1), so both are \equiv 0 and x, y are both even, again a contradiction. \square
- Proof. If x^2 + y^2 = n, then (x + y)^2 + (x - y)^2 = 2n. If u^2 + v^2 = 2n, then u \equiv u^2 \equiv v^2 \equiv v \pmod 2, so x = (u + v)/2 and y = (u - v)/2 are integers with x^2 + y^2 = n. The two maps are inverse to each other, so they are bijections between the representations of n and those of 2n. \square
- Proof. Let P be the set of representations with x > 0, y \ge 0. The quarter-turn \rho(x, y) = (-y, x) preserves x^2 + y^2, and the regions \rho^k(\{x > 0, y \ge 0\}), k = 0, 1, 2, 3, cover the plane minus the origin without overlap; as n > 0, r_2(n) = 4|P|. If n is neither a square nor twice a square, no representation has y = 0 or x = y, so the swap (x, y) \mapsto (y, x) pairs the elements of P off with no fixed point. So |P| is even and 8 \mid r_2(n). \square
- Proof. By Theorems 4 and 5, p = a^2 + b^2 with a > b > 0. Theorem 2 with (c, d) = (a, b) gives p^2 = (a^2 - b^2)^2 + (2ab)^2, with a^2 - b^2 > 0 and 2ab > 0. Now let q^2 = x^2 + y^2. The Lemma gives x = qx' and y = qy', so x'^2 + y'^2 = 1, and one of x', y' is 0. \square
- Proof. An even square is 4t^2 \equiv 0 or 4 \pmod 8, and an odd square is 4t(t + 1) + 1 \equiv 1 \pmod 8 as t(t + 1) is even. Sums of three elements of \{0, 1, 4\} are 0, 1, 2, 3, 4, 5, 6, 8, 9, 12, which modulo 8 are 0, 1, 2, 3, 4, 5, 6, never 7. \square
- Proof. For a positive integer t let m = 2t^2 + 1 and n = m^2 - 1. Then n + 1 = m^2 + 0^2, n + 2 = m^2 + 1^2, and n = (m - 1)(m + 1) = 2t^2(2t^2 + 2), which is (2t^2)^2 + (2t)^2. So all three are sums of two squares, and distinct t give distinct n. For t = 1: 8, 9 and 10. \square