Sums of Squares

Iiro Kumpulainen, 587277

December 6, 2017

MS-E1110 Number Theory

1
Contents
1 Introduction 3

2 Sums of Two Squares 4

2.1 Sums of two squares for small values . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Closure under multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Primes p ≡ 1 mod(4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 The two-square theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Sums of Three Squares 7

3.1 Sums of three squares for small values . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Legendre’s three-square theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 Sums of Four Squares 8

4.1 Closure under multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Lagrange’s four-square theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2
1 Introduction
This paper discusses whether an integer n ∈ Z, n ≥ 0 can be represented as a sum of of squared
integers
n = x21 + x22 + ... + x2k , (1)
where x1 , x2 , ..., xk ∈ Z and the number of squares is fixed. In other words, we find the sets of
integers
Sk = {n | n = x21 + x22 + ... + x2k } (2)
for different values of k ∈ Z+ .

When k = 1, this is the set of integer squares

S1 = {02 , 12 , 22 , 32 , ...} = {0, 1, 4, 9, ...} (3)

We will be considering the cases k = 2, k = 3 and k = 4, and prove some defining properties for
these sets.
Ultimately, we will prove that all non-negative numbers can be represented as the sum of four
integers squares
S4 = N0 = {0, 1, 2, 3, ...}. (4)

3
2 Sums of Two Squares
2.1 Sums of two squares for small values
By trying out small values in the equation

n = x21 + x22 , (5)

we find the first numbers in the set

S2 = {n | n = x21 + x22 } = {0, 1, 2, 4, 5, 8, 9, 10, ...} (6)

so the numbers not in S2 are

3, 6, 7, 11, ... 6∈ S2 (7)

2.2 Closure under multiplication

Lemma 2.1. The set S2 is closed under multiplication, which means that if two integers x and y
can be represented as the sum of two squares, then their product xy can also be represented as the
sum of two squares.
Proof. Let x = a21 + b21 and y = a22 + b22 be sums of two squares. Now their product is

xy = (a21 + b21 )(a22 + b22 ) = a21 a22 + a21 b22 + b21 a22 + b21 b22 . (8)

On the other hand, (a1 a2 + b1 b2 )2 + (a1 b2 − b1 a2 )2 is the sum of two squares and

(a1 a2 +b1 b2 )2 +(a1 b2 −b1 a2 )2 = (a21 a22 +2a1 a2 b1 b2 +b21 b22 )+(a21 b22 −2a1 a2 b1 b2 +b21 a22 ) = a21 a22 +a21 b22 +b21 a22 +b21 b22 .
(9)
Now, by combining (7) and (8), we get

xy = (a1 a2 + b1 b2 )2 + (a1 b2 − b1 a2 )2 , (10)

which means the product of x and y can be represented as a sum of two squares.

2.3 Primes p ≡ 1 mod(4)

The following theorem was stated by Pierre de Fermat in 1640 and proved by Leonhard Euler in
1754 [JJ98].
Theorem 2.2. All primes p ≡ 1 mod(4) can be represented as the sum of two squares.

a
Proof. Let p be a prime such that p ≡ 1 mod(4). Euler’s criterion states that = 1 if and only
p
if p−1
a 2 ≡ 1 mod(p), (11)

a
where is the Legendre symbol
p

 0,
 if a ≡ 0 modulo p
a
= 1, if a is a square 6= 0 modulo p (12)
p 
−1, otherwise


p−1
Now p ≡ 1 mod(4) so 2 is even. Therefore by applying Euler’s criterion to a = −1 we get

p−1 −1
(−1) 2 ≡ 1 mod(p) ⇐⇒ = 1. (13)
p

Therefore −1 is a square modulo p, which means that there is an integer u such that 0 ≤ u ≤ p − 1
and
u2 ≡ −1 mod(p) (14)

4
u2 + 1 ≡ 0 mod(p) (15)
This means that there is an integer r such that 0 < r < p and
u2 + 1 = rp (16)
Thus, rp is the sum of two squares
rp = u2 + 12 ∈ S2 (17)
Now there is a smallest integer m such that mp ∈ S2 . If m = 1 then p ∈ S2 , which we wanted to
prove. We can then assume that m > 1.
Now mp ∈ S2 so mp = a21 + b22 for some integers a1 and b1 . Let a2 and b2 now be the least
absolute residues of a1 and b1 modulo m. In other words, let a2 and b2 be the numbers such that
m2
a2 ≡ a1 and b2 ≡ b1 mod(m) and |a2 |, |b2 | ≤ m 2 2 m 2
2 . This means that a2 + b2 ≤ 2( 2 ) = 2 Now
2
a22 + b22 ≡ a21 + b21 ≡ mp ≡ 0 mod(m) so a22 + b22 = sm for some s ∈ Z. Then sm = a22 + b22 ≤ m2 ,
so s ≤ m 2 , which means that s < m.
If s = 0 then a22 + b22 = sm = 0, so a2 = b2 = 0. Then a1 ≡ a2 ≡ 0 mod(m) and b1 ≡ b2 ≡ 0
mod(m). Thus m2 | a21 and m2 | b21 , and therefore m2 | a21 + b21 = mp, which means that m | p.
This is a contradiction, since 1 ≤ m ≤ p and p is a prime. Therefore 0 ≤ s ≤ m.
Now (a21 + b21 )(a22 + b22 ) = (mp)(sm) = m2 sp and from the proof of Lemma 2.1 we get that
m2 sp = (a21 + b21 )(a22 + b22 ) = (a1 a2 + b1 b2 )2 + (a1 b2 − b1 a2 )2 . (18)
Since a1 a2 + b1 b2 ≡ a21 + b21 ≡ mp ≡ 0 mod(m), (a1 a2 + b1 b2 ) is divisible by m so a1 b2 − b1 a2 must
−b1 a2 2
also be divisible by m. This means that ( a1 a2m ) and ( a1 b2m
+b1 b2 2
) are integer squares and by
2
dividing both sides of (18) by m we get
a1 a2 + b1 b2 2 a1 b2 − b1 a2 2
sp = ( ) +( ) . (19)
m m
Therefore, sp is the sum of two squares, which is a contradiction because m is the smallest positive
integer such that mp ∈ S2 but now sp ∈ S2 and 0 ≤ s ≤ m. Therefore the assumption that m ≥ 1
is false and m = 1 so mp = p can be represented as the sum of two squares.

2.4 The two-square theorem

Theorem 2.3. n ∈ S2 ⇐⇒ all primes q such that q ≡ 3 mod(4) have an even exponent in the
prime factorization of n.
Proof.
If all primes q such that q ≡ 3 mod(4) have an even exponent in the prime factorization of n
then we can write
αk 2β1 αk 2 β1
n = 2α pα 1 2βm
1 ... pk q1 ... qm = 2α pα 2 βm
1 ... pk (q1 ) ... (qm )
1
, (20)
where pi are primes pi ≡ 1 mod(4), qj are primes qj ≡ 3 mod(4) and the exponents α ≥ 0 and
αi , βj ∈ Z+ for all i ∈ {1, ..., k}, j ∈ {1, ..., m}. Now n is a product of elements of S2 . This is
because the primes pi ∈ S2 by theorem 2.2 and each of the squares qj2 = qj2 + 02 ∈ S2 and also
2 = 12 + 12 ∈ S2 . And by Lemma 2.1, the set S2 is closed under multiplication, so also n ∈ S2 .
If n ∈ S2 then we can write n = x2 + y 2 for some integers x and y. If n does not have any prime
factors q such that q ≡ 3 mod(4), then are done. Otherwise let q be any of such prime factors.
Let α be the exponent of q in the prime factorization of n and suppose that α is odd. Let d be
the greatest common divisor of x and y, which means that x = ad and y = bd for some integers
a and b such that gcd(a, b) = 1. Then n = x2 + y 2 = (a2 + b2 )d2 so dn2 = a2 + b2 . Let β is the
exponent of q in the prime factorization of d. Now q α−2β | dn2 and since α − 2β is odd, it must be
α − 2β 6= 0. This means that q | dn2 = a2 + b2 so

a2 ≡ −b2 mod(q) (21)

If q | b, then q divides both a and b which is a contradiction, because gcd(a, b)= 1. Therefore q - b
and since q is a prime, b has a multiplicative inverse modulo q. Let c be the inverse of b modulo
q. Now by multiplying both sides of (21) by c2 we get
(ac)2 ≡ −b2 c2 ≡ −1 mod(q) (22)

5
Therefore −1 is a square modulo q. However, q ≡ 3 mod(4) so q−1
2 is odd so by applying Euler’s
criterion to −1 we get
q−1 −1
(−1) 2 ≡ −1 mod(q) ⇐⇒ = 1, (23)
q
which means that −1 is not a square modulo q. This is a contradiction so the assumption that α
is odd must be false, which means that all primes q such that q ≡ 3 mod(4) have an even exponent
in the prime factorization of n.

6
3 Sums of Three Squares
3.1 Sums of three squares for small values
Let’s now consider the set of numbers that can be represented as the sum of three squares

S3 = {n | n = x21 + x22 + x23 }. (24)

The smallest values that can not be represented as the sum of three squares are

7, 15, 23, 28, 31, 39, ... 6∈ S3 . (25)

Corollary 3.0.1. The set of numbers that can be represented as the sum of three squares is not
closed under multiplication.
Proof. The numbers 3 = 12 + 12 + 12 and 5 = 02 + 12 + 22 can be represented as the sum of three
squares, while 15 = 3 × 5 can not. Therefore, the set S3 is not closed under multiplication.

3.2 Legendre’s three-square theorem

The following theorem, known as Legendre’s three-square theorem, was proven by Adrien-Marie
Legendre and Carl Friedrich Gauss.

Theorem 3.1. n ∈ S3 ⇐⇒ n 6= 4a (8b + 7) for any a, b ∈ Z

The proof of this theorem is omitted here as the proof is quite complicated. This case is very
different from cases k = 2 and k = 4 because the set S3 is not closed under multiplication.

7
4 Sums of Four Squares
4.1 Closure under multiplication
Lemma 4.1. The set S4 = {n | n = x21 + x22 + x23 + x24 } is closed under multiplication, which means
that if two integers x and y can be represented as the sum of four squares, then their product xy
can also be represented as the sum of four squares.
Proof. Let x = a21 + b21 + c21 + d21 and y = a22 + b22 + c22 + d22 be sums of two squares. Now their
product is

xy = (a21 + b21 + c21 + d21 )(a22 + b22 + c22 + d22 ) = a21 a22 + a21 b22 + a21 c22 + a21 d22 + b21 a22 + b21 b22 + b21 c22 + b21 d22
+ c21 a22 + c21 b22 + c21 c22 + c21 d22 + d21 a22 + d21 b22 + d21 c22 + d21 d22 . (26)

On the other hand, (a1 a2 + b1 b2 + c1 c2 + d1 d2 )2 + (a1 b2 − b1 a2 − c1 d2 + d1 c2 )2 + (a1 c2 + b1 d2 −

c1 a2 − d1 b2 )2 + (a1 d2 − b1 c2 + c1 b2 − d1 a2 )2 is the sum of four squares and

(a1 a2 + b1 b2 + c1 c2 + d1 d2 )2 + (a1 b2 − b1 a2 − c1 d2 + d1 c2 )2 +
(a1 c2 + b1 d2 − c1 a2 − d1 b2 )2 + (a1 d2 − b1 c2 + c1 b2 − d1 a2 )2 =
(a21 a22 + b21 b22 + c21 c22 + d21 d22 + 2(a1 a2 b1 b2 + a1 a2 c1 c2 + a1 a2 d1 d2 + b1 b2 c1 c2 + b1 b2 d1 d2 + c1 c2 d1 d2 ))+
(a21 b22 + b21 a22 + c21 d22 + d21 c22 + 2(−a1 b2 b1 a2 − a1 b2 c1 d2 + a1 b2 d1 c2 + b1 a2 c1 d2 − b1 a2 d1 c2 − c1 d2 d1 c2 ))+
(a21 c22 + b21 d22 + c21 a22 + d21 b22 + 2(a1 c2 b1 d2 − a1 c2 c1 a2 − a1 c2 d1 b2 − b1 d2 c1 a2 − b1 d2 d1 b2 + c1 a2 d1 b2 ))+
(a21 d22 + b21 c22 + c21 b22 + d21 a22 + 2(−a1 d2 b1 c2 + a1 d2 c1 b2 − a1 d2 d1 a2 − b1 c2 c1 b2 + b1 c2 d1 a2 − c1 b2 d1 a2 )) =
a21 a22 +a21 b22 +a21 c22 +a21 d22 +b21 a22 +b21 b22 +b21 c22 +b21 d22 +c21 a22 +c21 b22 +c21 c22 +c21 d22 +d21 a22 +d21 b22 +d21 c22 +d21 d22 .
(27)

Now, by combining (26) and (27), we get

xy = (a1 a2 + b1 b2 + c1 c2 + d1 d2 )2 + (a1 b2 − b1 a2 − c1 d2 + d1 c2 )2 +
(a1 c2 + b1 d2 − c1 a2 − d1 b2 )2 + (a1 d2 − b1 c2 + c1 b2 − d1 a2 )2 , (28)

which means the product of x and y can be represented as a sum of four squares.

4.2 Lagrange’s four-square theorem

Theorem 4.2. Every non-negative number can be represented as the sum of four squares.
Proof. Clearly 0, 1, and 2 ∈ S4 so by applying the closure under multiplication from Lemma 4.1
and the prime factorization of integers, it is sufficient to prove that every odd prime is in S4 .
Let p be an odd prime, which means that it has p−1 2 quadratic residues. By including 0,
we get that p+1 2 of the numbers Z p = {0, 1, ..., p − 1} are squares. Therefore the set K =
p+1
2

z ∈ Zp | z = k , k ∈ Zp contains 2 elements and a similar argument shows that the set L =
z ∈ Zp | z = −1 − n2 , n ∈ Zp also has p+1

2 elements. Since both of these sets have more than
half of the elements in Zp , their intersection can not be empty. This means that there is an in-
teger z ∈ Zp that belongs to both sets K and L. Therefore there are integers u and v such that
u2 ≡ −1 − v 2 mod(p) so u2 + v 2 + 1 = rp for some integer r > 0. Thus p has some multiple
rp = u2 + v 2 + 1 = u2 + v 2 + 12 + 02 that can be represented as the sum of four squares. By
replacing u and v with their least absolute residues mod(p) we may assume that |u| ,|v| ≤ p2 , so
2
rp = u2 + v 2 + 1 ≤ 2( p2 )2 + 1 = p2 + 1 < p2 so r < p. This means that there is a smallest positive
integer m < p such that mp ∈ S4 . Let

mp = a21 + b21 + c21 + d21 . (29)

If m = 1 then p ∈ S4 and we are done.

Assume now that m > 0. Let the least absolute residues of a1 , b1 , c1 , and d1 be a2 , b2 , c2 , and
d2 respectively. Now a22 + b22 + c22 + d22 ≡ a21 + b21 + c21 + d21 ≡ 0 mod(m) so, in the same manner as
in the proof of Theorem 2.2 we get that

a22 + b22 + c22 + d22 = sm (30)

8
for some integer s.
If now m is odd then the inequalities for the least absolute residues become |a2 |, |b2 |, |c2 |,
|d2 | ≤ m−1 2 <m 2 2 2 2 m 2 2
2 . Thus sm = a2 + b2 + c2 + d2 < 4( 2 ) = m and s < m.
If instead m is even, then from equation (29) we get that all, or two or none of the numbers a1 ,
b1 , c1 , and d1 are odd. By renaming the variables we may assume that a1 and b1 have the same
parity and same for c1 and d1 . Then a1 ± b1 and c1 ± d1 are even, which means that

a1 + b1 2 a1 − b1 2 c1 + d1 2 c1 − d1 2 a2 + b21 + c21 + d21 mp

( ) +( ) +( ) +( ) = 1 = (31)
2 2 2 2 2 2
is a sum of four squares. So m2 p ∈ S4 , which is a contradiction to the minimality of m. Therefore
m is odd and s < m.
If s = 0, then from equation (30) we get that a2 = b2 = c2 = d2 = 0 so a1 , b1 , c1 , and d1 are
all divisible by m so from equation (29) we get that mp is divisible by m2 , which implies that p
is divisible by m. This is not possible, because p is a prime and 1 < m < p. Therefore we have
0 < s < m.
From equations (29) and (30) we get that

(a21 + b21 + c21 + d21 )(a22 + b22 + c22 + d22 ) = (mp)(sm) = m2 sp (32)

From the proof of Lemma 4.1 we get that

m2 sp = (a1 a2 + b1 b2 + c1 c2 + d1 d2 )2 + (a1 b2 − b1 a2 − c1 d2 + d1 c2 )2 +
(a1 c2 + b1 d2 − c1 a2 − d1 b2 )2 + (a1 d2 − b1 c2 + c1 b2 − d1 a2 )2 (33)

The congruences a1 ≡ a2 mod(m), etc., and the equation (30), show that

a1 a2 + b1 b2 + c1 c2 + d1 d2 ≡ (a22 + b22 + c22 + d22 ) ≡ 0 mod(m), (34)

a1 b2 − b1 a2 + c1 d2 + d1 c2 ≡ (a2 b2 − b2 a2 − c2 d2 + d2 c2 ) ≡ 0 mod(m), (35)

and so on, so each of the squared terms in equation (33) is divisible by m. So by dividing both
sides of (33) by m2 we get

a1 a2 + b1 b2 + c1 c2 + d1 d2 2 a1 b2 − b1 a2 − c1 d2 + d1 c2 2
sp = ( ) +( ) +
2 2
a1 c2 + b1 d2 − c1 a2 − d1 b2 2 a1 d2 − b1 c2 + c1 b2 − d1 a2 2
( ) +( ) (36)
2 2
so sp can be represented as the sum of four squares. Since 0 < s < m this is a contradiction to the
minimality of m, so the assumption that m > 1 is false. Therefore m = 1 and p ∈ S4 .

9
References
[JJ98] Gareth A Jones and Josephine M Jones. Elementary number theory. Springer Science &
Business Media, 1998.

10