1.28: Sum of Squares

In this chapter we present the answers to the first question asked in the first chapter of this book: which positive integers can be expressed as the sum of two, three, or four perfect squares?

Sums of two squares

Shown here is the list of the integers from 0 to 100 that can be written as a sum of two squares, organized into two sets of four columns, with spaces marking integers that are not equal to the sum of two squares.

Figure \(\PageIndex{1}\)

A few patterns seem to jump out immediately:

• We see no number that is congruent to 3 modulo 4.
• In the second column we see mostly numbers that are separated by some multiple of 8—so we see no number that is congruent to 6 modulo 8.

Now numbers that are congruent to 6 modulo 8 are 2 times numbers that are congruent to 3 modulo 4, so perhaps whether a number does or does not appear depends on the prime factorization of the number. Indeed, the third column contains none of the primes 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, or 83, and many—in fact all—of the numbers missing from the list have one of these primes as a prime factor. In fact,

• The only multiples of 3 appearing in the list are 9, 18, 36, 45, 72, 81, 90—the multiples of 9 (\(=3^2\)) but not of 27 (\(=3^3\)), except for 81 (\(=3^4\)).
• The only multiples of 7 appearing in the list are 49 and 98—the multiples of 49 (\(=7^2\)).
• No multiple of 11, 19, or any of the other missing primes appears in the list (though clearly if we extended the list, then \(121 = 11^2 + 0^2\) would appear on the list).

Examining how these patterns continue among higher numbers, we might arrive at the following statement, which we will partially justify in this section.

Theorem \(\PageIndex{1}\): Sum of 2 Squares

A positive integer \(n\) is equal to the sum of two perfect squares if and only if the prime factorization of \(n\) contains no odd exponent on any prime that is congruent to \(3\) modulo \(4\).

Why might this be true? While a full proof would need more preparation than we will give in this text, We can establish a few helpful lemmas to hint at where this theorem comes from.

Lemma \(\PageIndex{1}\)

If \(a\) and \(b\) can both be written as the sum of two squares, then \(ab\) can also be written as the sum of two squares.

Proof

Suppose that \(a = w^2+x^2\) and \(b = y^2+z^2\). We use a factoring trick from the Gaussian integers: \[a = w^2 - (-x^2) = (w+ix)(w-ix); \qquad b = y^2 - (-z^2) = (y+iz)(y-iz).\nonumber \] \[\begin{aligned} ab &= (w+ix)(w-ix)(y+iz)(y-iz)\\ &= [(w+ix)(y+iz)][(w-ix)(y-iz)]\\ &= [(wy-xz) + i(wz+xy)][(wy-xz)-i(wz+xy)]\\ &= (wy-xz)^2 + (wz+xy)^2. \end{aligned}\] Since \(wy-xz\) and \(wz+xy\) are integers, \(ab\) is a sum of two squares.

Because of this lemma, if we can determine which powers of primes can be written as sums of two squares, then we’ll be a lot closer to showing that Theorem \(\PageIndex{1}\) is correct. The easiest statement is this:

Proposition \(\PageIndex{1}\)

If \(p\) is a prime and \(n\) is a nonnegative integer, then \(p^{2n} = \left(p^n\right)^2+0^2\), so any prime raised to an even power can be written as the sum of two squares.

Here’s another piece of the puzzle.

Lemma \(\PageIndex{2}\)

If \(n \equiv 3 \pmod 4\), then \(n\) cannot be written as a sum of two squares.

Proof

Observe that for any integer \(k\), \[(2k)^2=4k^2\quad\text{and}\quad (2k+1)^2=4k^2+4k+1=4(k^2+k)+1,\nonumber\] so even numbers have squares that are congruent to 0 modulo 4, and odd numbers have squares that are congruent to 1 modulo 4. Hence the sum of two squares can be congruent to either \(0\) (\(=0+0\)) or \(1\) (\(=0+1\)) or \(2\) (\(=1+1\)), but it cannot be congruent to \(3\) modulo 4.

To complete the proof of Theorem \(\PageIndex{1}\), we would need to show the following:

• Every prime that is congruent to 1 modulo 4 can be written as a sum of two squares. (This statement was made by A. Girard in 1632, and again by Fermat, who claimed in a 1654 letter to Pascal to have a proof, though we don’t have a record of it; Euler published a proof in 1758.)
• If \(n\) has a prime factorization where some prime that is congruent to 3 modulo 4 is raised to an odd exponent, then \(n\) cannot be written as a sum of two squares.

Proofs of both of these statements are made possible through the study of quadratic residues. These are simply the numbers that occur as perfect squares with respect to a given modulus; for instance, modulo 10, the quadratic residues are \(0\), \(1\), \(4\), \(9\), \(6\), \(5\) (but not \(2\), \(3\), \(7\), or \(8\)—these never show up as the units digit in a perfect square). There is a wealth of interesting properties and results related to quadratic residues that is just barely beyond the scope of this book. You are encouraged to look these up in a bit more advanced of a text and do some reading on your own. In the meantime, we will move on now to the next problem.

Sums of three squares

As we did in the previous section, let’s start by listing the nonnegative integers that are at most 100 and able to be written as the sum of three squares. Recalling from Section 1.1 that 7, 15, and 23 could not be written in this way, we put our list in 8 columns.

Figure \(\PageIndex{2}\)

Here the patterns are even starker:

• We see no number that is congruent to 7 modulo 8.
• The only other missing numbers belong to the 4th column, where they are \(28\) (\(=4\cdot 7\)), 60 (\(=4\cdot 15\)), and 92 (\(=4\cdot 23\)); these numbers are each 4 times a number that is congruent to 7 modulo 8.

The last observation suggests that again factorizations of a number may make a difference in expressibility as a sum of squares.

In fact, the correct statement, proved by Legendre in 1797 or 1798, is this:

Theorem \(\PageIndex{2}\): The Sum of 3 Squares

A positive integer \(n\) is equal to the sum of three perfect squares if and only if \(n\) does not have the form \(4^a(8b+7)\).

Like that of Theorem \(\PageIndex{1}\), this proof is beyond our grasp at the moment, but once again we will say what we can. We start with a simple corollary to Theorem \(\PageIndex{1}\).

Proposition \(\PageIndex{2}\)

Any number that can be written as the sum of two squares can be written as the sum of three squares, since if \(n=a^2+b^2\) then \(n=a^2+b^2+0^2\). Hence we may write as the sum of three squares any \(n\) for which the prime factorization of \(n\) contains no odd exponent on any prime that is congruent to 3 modulo 4.

We may also write as the sum of three squares any number that is 1 more than a number that is the sum of two squares, since if \(n=a^2+b^2\), then \(n+1=a^2+b^2+1^2\).

As look at the gaps in our list above, we see that numbers that are congruent to 7 modulo 8 are all congruent to 3 modulo 4 and so are not expressible as the sum of two squares. We also note that each gap in our list corresponds to a gap of at least two consecutive numbers in the list of two-squares numbers in the last section.

We turn to explaining why some numbers cannot be written as the sum of three squares.

Lemma \(\PageIndex{3}\)

If \(n \equiv 7 \pmod 8\), then \(n\) cannot be written as a sum of three squares.

Proof

See Exercise \(\PageIndex{4}\).

Lemma \(\PageIndex{4}\)

No integer of the form \(4^a(8b+7)\), where \(a\) and \(b\) are nonnegative integers, is equal to the sum of three squares.

Proof

We prove the result by induction on \(a\). Observe that if \(a=0\), then \(4^a(8b+7)\) cannot equal the sum of three squares by Lemma \(\PageIndex{3}\). Suppose now that no integer of the form \(4^s(8m+7)\), where \(m\) is an integer, is equal to the sum of three squares for any \(s \in \{0,1,\dots,k\}\), where \(k\) is a nonnegative integer. Let \(n=4^{k+1}(8b+7)\), and suppose to the contrary that \(n = p^2+q^2+r^2\) for integers \(p,q,r\). Now \(n \bmod 8 \in \{0,4\}\), and it can be shown (see Exercise \(\PageIndex{4}\)) that each of \(p^2,q^2,r^2\) is congruent to \(0\) or \(1\) or \(4\) modulo 8. The only way these numbers can sum to 0 or 4 modulo 8 is by having them all be congruent to 0, or two congruent to 0 and one congruent to 4, or all congruent to 4, modulo 8. In each case, each of \(p^2,q^2,r^2\) is divisible by 4, and hence each of \(p,q,r\) is divisible by 2. We may thus write \(p=2p'\), \(q=2q'\), and \(r=2r'\), where \(p',q',r'\) are integers, and thus \[n = (2p')^2+(2q')^2+(2r')^2 = 4[(p')^2+(q')^2+(r')^2],\nonumber \] and hence the integer \(n/4\) can be written as a sum of three squares: \[4^{k}(8b+7) = (p')^2+(q')^2+(r')^2.\nonumber \] Since the exponent on \(4\) above makes the left-hand side fit our induction hypothesis, this is a contradiction. Hence by PMI, no integer of the form \(4^a(8b+7)\), where \(a\) and \(b\) are nonnegative integers, is equal to the sum of three squares.

To complete the proof of Theorem \(\PageIndex{2}\), we would need to show that every number \(n\) that is not of the form \(4^a(8b+7)\) can be written as the sum of three squares. This result is quite a bit more involved than either the two-square theorem of the last section or the four-square theorem in the next section. Its proofs, like the two-square theorem’s proof, often make use of properties of quadratic residues (and in particular, a theorem known as the the law of quadratic reciprocity) that are beyond the scope of this book, but which are worth pursuing, if you are interested.

Sums of four squares

In Section 1.1 we identified no positive integer that could not be written as the sum of four squares. This is no accident.

Theorem \(\PageIndex{3}\): Sum of 4 Squares

Every positive integer \(n\) is equal to the sum of four perfect squares.

This statement is believed to have been known (though without proof) by Diophantus, based on examples in the Arithmetica; a proof was given by Lagrange in 1770.

Once the three-square theorem (Theorem \(\PageIndex{2}\)) was proved by Legendre in 1797–1798, the four-square theorem became a corollary, as we now show.

Proof of Theorem \(\PageIndex{3}\)

Proof

Let \(n\) be any positive integer. If \(n=a^2+b^2+c^2\) for integers \(a,b,c\), then \(n=a^2+b^2+c^2+0^2\). If \(n\) cannot be written as the sum of three perfect squares, then \(n\) has the form \(4^k(8\ell+7)\) for nonnegative integers \(k,\ell\). The number \(4^k(8\ell+6)\) does not have this form (the exponent on 2 in the prime factorization is odd, while the exponent on 2 is even in the prime factorization of \(4^k(8\ell+7)\)). Thus there exist integers \(a,b,c\) such that \(4^k(8\ell+6) = a^2+b^2+c^2\), and \[n=4^k(8\ell+7) = 4^k(8\ell+6) + 4^k = a^2+b^2+c^2+(2^{k})^2.\nonumber \] Hence \(n\) may always be written as the sum of four squares.

However, Lagrange’s proof predates Legendre’s proof by nearly two decades, and it is much simpler. We will not give the full proof here—once again, it involves facts about quadratic residues that we do not currently have—but we will mention a four-square analogue of the trick in Lemma \(\PageIndex{1}\) that is useful here as well.

Lemma \(\PageIndex{5}\): Product of 4 Sums

If \(a\) and \(b\) can both be written as the sum of four squares, then \(ab\) can also be written as the sum of four squares.

Proof

Suppose that \(a = a_1^2+a_2^2+a_3^2+a_4^2\) and \(b = b_1^2+b_2^2+b_3^2+b_4^2\). Tedious though straightforward algebra verifies that \[\begin{aligned} ab &= (a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)\\ &= \phantom{+}(a_1b_1-a_2b_2-a_3b_3-a_4b_4)^2 \\ &\phantom{=} +(a_1b_2+a_2b_1+a_3b_4-a_4b_3)^2\\ &\phantom{=} +(a_1b_3-a_2b_4+a_3b_1+a_4b_2)^2\\ &\phantom{=} +(a_1b_4+a_2b_3-a_3b_2+a_4b_1)^2. \end{aligned}\] Each of the quantities inside a matched pair of parentheses is an integer, so \(ab\) is the sum of four squares.\(^{1}\)

It follows that if we can show that every prime is the sum of four squares, then every positive integer can be written as the sum of four squares. Results from the study of quadratic residues do allow us to prove the four-squares result for primes, and Theorem \(\PageIndex{3}\) follows.

As we conclude this chapter, we mention that the results of this chapter tie in with Waring’s problem, proposed in 1770 (the same year as Lagrange’s four-square theorem proof) by Edward Waring. Waring’s problem asks whether every power \(k\) has an associated number \(t_k\) such that every positive integer can be expressed as the sum of \(t_k\) \(k\)-th powers. For example, when \(k=2\), we have shown that we can take \(t_2=4\), since every number can be written as the sum of four perfect squares. Must \(t_k\) exist for every \(k\)? The answer is yes, as shown by David Hilbert in 1909.

Other similar results exist. For example, Fermat stated in 1638 (again, without proof) that every positive integer is a sum of at most \(n\) different \(n\)-gonal numbers, where an \(n\)-gonal number or polygonal number is a number that counts the number of dots used when the dots are arranged in “shells” shaped like a regular \(n\)-gon. The triangular numbers of Exercise 1.3.14 are an example. In Gauss’s mathematical diary on July 10, 1796, he is reported to have written, using Greek and some personal symbolic shorthand,

\(\mathrm{E}\Upsilon\mathrm{P}\mathrm{E}\mathrm{K}\mathrm{A}\)! \(\mathrm{num} = \Delta\) + \(\Delta\) + \(\Delta\).

This result is accordingly called Gauss’s “Eureka Theorem”; in words, it states that every positive integer can be written as the sum of at most three triangular numbers. Of course Theorem \(\PageIndex{3}\), Lagrange’s 1770 result, shows that every positive integer can be written as the sum of at most four square numbers. Finally, Fermat’s polygonal number claim was proved for all \(n\) by Cauchy in 1813.

These theorems highlight a special property of these numbers. By way of contrast, observe that though every positive integer can be written as a sum of integral powers of 2 (or any greater integer base—this was Theorem 1.6.1), we cannot always do it with three powers of 2, or four, or even ten powers of 2. The number of summands necessary quickly grows larger than any particular finite number—in fact, \(2^n-1\) will always need at least \(n\) summands, no matter how big \(n\) gets. So square numbers and polygonal numbers somehow possess useful properties that powers of an integer do not. There’s probably a lesson there...or maybe even a research question.

Exercises

Exercise \(\PageIndex{1}\)

Which of the following may be written as a sum of two squares? For any that cannot, give a detailed justification of why not. For any that can, list two numbers whose squares add up to the given number.

1. 315
2. 569
3. 100,000
4. 54,925.

Exercise \(\PageIndex{2}\)

Prove that the norm of a Gaussian integer can never be congruent to 3 modulo 4.

Exercise \(\PageIndex{3}\)

Prove that a prime integer that is congruent to 1 modulo 4 is never a Gaussian prime (as defined in Section 1.13).

(Hint: as part of your answer, recall how sums of squares can be factored in the Gaussian integers.)

Exercise \(\PageIndex{4}\)

Show that no integer of the form \(8b+7\) is equal to the sum of three squares.

(Hint: Follow the spirit of the proof of Lemma \(\PageIndex{2}\), looking at the possible residues of \(a^2+b^2+c^2\), modulo 8, over all the possible cases for the remainders when \(a,b,c\) are divided by 4.)

Exercise \(\PageIndex{5}\)

Which of the following may be written as a sum of three squares? For any that cannot, give a detailed justification of why not. For any that can, list three numbers whose squares add up to the given number.

1. 331
2. 156
3. 76.

Exercise \(\PageIndex{6}\)

Write each of the numbers \(n\), for \(30 \leq n \leq 40\), as a sum of squares, in each case using as few squares as possible.

Exercise \(\PageIndex{7}\)

(For students who have seen matrices and determinants.) In many ways, the matrices of the form \(\begin{bmatrix}a & b\\-b & a\end{bmatrix}\), where \(a,b \in \mathbb{Z}\), behave like Gaussian integers \(a+bi\). (To see this, add and multiply \(a+bi\) and \(c+di\), and compare the results to the sum and product of \(\begin{bmatrix}a & b\\-b & a\end{bmatrix}\) and \(\begin{bmatrix}c & d\\-d & c\end{bmatrix}\).) Now the determinant of \(\begin{bmatrix}a & b\\-b & a\end{bmatrix}\) is \(a^2+b^2\), which equals \((a+bi)(\overline{a+bi})\) and also equals a sum of two squares. This gives us another way to derive the identity in Lemma \(\PageIndex{1}\), which you will now carry out:

Compute the determinant of \(\begin{bmatrix}a & b\\-b & a\end{bmatrix}\begin{bmatrix}c & d\\-c & d\end{bmatrix}\) by multiplying the matrices and afterwards finding the determinant. Then use the property \(\det XY = (\det X)(\det Y)\) of matrices to conclude Lemma \(\PageIndex{1}\).

Exercise \(\PageIndex{8}\)

(For students who have seen matrices and determinants.) When we tweak the matrices used in the previoius exercise, we get even more interesting results. Matrices of the form \(\begin{bmatrix}a+bi & c+di\\-c-di & a-bi\end{bmatrix}\), where \(a,b,c,d \in \mathbb{Z}\), behave like elements of a number system known as the quaternions, where numbers have the form \(a+b\mathbf{i}+c\mathbf{j}+d\mathbf{k}\) for special symbols \(\mathbf{i},\mathbf{j},\mathbf{k}\) that, like the imaginary number \(i\), have certain special properties. A quick search of the internet will reveal details of computing with quaternions; do some reading on your own, if you wish. The quaternions can be used to prove Lemma \(\PageIndex{5}\) in the same way the Gaussian integers were used to prove Lemma \(\PageIndex{1}\). However, for simplicity(?), we will work with the matrix analogues of the quaternions, which involve only matrices with Gaussian integer entries.

Now the determinant of \(\begin{bmatrix}a+bi & c+di\\-c-di & a-bi\end{bmatrix}\) is \(a^2+b^2+c^2+d^2\), a sum of four squares. We can use this in a similar manner as in the previous exercise.

Compute the determinant of \(\begin{bmatrix}a_1+a_2i & a_3+a_4i\\-a_3+a_4i & a_1-a_2i\end{bmatrix}\begin{bmatrix}b_1+b_2i & b_3+b_4i\\-b_3+b_4i & b_1-b_2i\end{bmatrix}\) by multiplying the matrices and afterwards finding the determinant. Then use the property \(\det XY = (\det X)(\det Y)\) of matrices to conclude Lemma \(\PageIndex{5}\).

Footnotes

[1] This identity was included in a letter that Euler wrote to Goldbach in 1748. Like the proof of Lemma \(\PageIndex{1}\), there is a way to arrive at this identity in an almost straightforward way by using a different set of numbers. Instead of Gaussian integers and complex conjugates, though, the numbers and concept we need here are the quaternions and quaternion conjugates. Look these up! Or for an alternative proof, see Exercise \(\PageIndex{8}\).