The theorem that characterises those integers that are the sum of 3 squares appears not to be easily findable on the Web. I therefore present a proof here. It is based on that in [R].
Theorems referred to:
Some theory about quadratic residues and quadratic forms is needed.
Theorem (Legendre 1798): A non-negative integer m is the sum of 3 squares iff it is not of the form 4a(8k+7).
Proof: Modulo 4, every square ≡ 0 or 1. Thus the only way the sum of 3 squares can ≡ 0 is 0+0+0. Thus if 4n is the sum of 3 squares, then
| 4n | = (2a)2 + (2b)2 + (2c)2 | |
⇔ | n | = a2 + b2 + c2 |
Thus n is the sum of 3 squares iff 4n is.
Thus if 4 divides m, apply the theorem to m/4; m is the sum of 3 squares iff m/4 is.
Modulo 8, every square ≡ 0, 1 or 4. Thus these can give totals in the following ways:
1 ≡ 0+0+1 ≡ 4+4+1
2 ≡ 0+1+1
3 ≡ 1+1+1
5 ≡ 0+4+1
6 ≡ 4+1+1
Thus an integer of the form 8k+7 is not the sum of 3 squares. This proves the "only if" part of the theorem.
The rest of this proof follows [R].
Let
F(x, y, z) = ax2 + by2 + cz2 + 2dyz + 2exz + 2fxy
be a ternary quadratic form such that D(F) = 1.
Let C = ab−f2 ___ [1]
Lemma 1. F is
positive definite iff a>0 and C>0.
Proof: [if] Suppose a>0 and C>0. Then
| F(x, y, z) | = ax2 + by2 + cz2 + 2dyz + 2exz + 2fxy | |
| ⇒ | Ca F(x, y, z) | = Ca2x2 +a2b2y2 −abf2y2 +a2bcz2 −acf2z2 +2a2bdyz −2adf2yz +2a2bexz −2aef2xz + 2Cafxy |
| = Ca2x2 + abf2y2 −f4y2 + abe2z2 −e2f2z2 + 2abefyz −2ef3yz +2a2bexz −2aef2xz + 2Cafxy +a2b2y2 −2abf2y2 +f4y2 +2a2bdyz −2abefyz −2adf2yz +2ef3yz + a2d2z2 −2adefz2 +e2f2z2 +a2bcz2 +2adefz2 −a2d2z2 −abe2z2 −acf2z2, where italicised terms have been added and cancel each other | ||
| = (ab−f2)(a2x2 +f2y2 +e2z2 +2efyz +2aexz +2afxy ) + (aby−f2y+adz−efz)2 + az2, using D(F) = 1 to simplify the last 5 terms | ||
| = (ab−f2)(ax+fy+ez)2 + ((ab−f2)y+adz−efz)2 + az2 | ||
| = C(ax+fy+ez)2 + [Cy+(ad−ef)z]2 + az2 |
which is positive unless x=y=z=0.
[only if] If a≤0, F(1, 0, 0) = a ≤ 0. If a>0 and C≤0,
F(x, y, 0) = {(ax+fy)2 + Cy2}/a
which has nonpositive values if ab is large enough. []
To prove the theorem, it is sufficient to find, for each relevant m, a ternary quadratic form F and values X, Y, Z such that
F(X, Y, Z) = m ___ [2]
a > 0 ___ [3]
C > 0 ___ [4]
D(F) = 1 ___ [5]
Here is one solution: If
X = Y = 0
Z = 1
c = m
d = 0
e = 1
then
F(X, Y, Z) = F(0, 0, 1) = m
satisfying [2]. Condition [5] reduces to
D(F) = Cm−b = 1 ___ [6]
The theorem is clearly true for m=1. For m>1,
| C+f2 | = ab | (from [1]) | |
| = a(Cm−1) | (from [6]) | ||
| ⇒ | f2 | = a(Cm−1) − C | ___ [7] |
which implies [3] It is sufficient to find an integer q>0 where −q is a square, modulo qm−1, giving us f from [7].
If m is even, then, by Dirichlet's theorem, there is a prime p and integer t>=0 where
p = 4mt + m − 1
Let q = 4t+1. Then
p = qm − 1
Modulo 4, p ≡ 1 and q ≡ 1, so, by the quadratic reciprocity theorem,
| (−q\p) | = (−1\p)(q\p) | as quadratic residues are multiplicative |
| = (q\p) | as p ≡ 1 | |
| = (p\q) | by the quadratic reciprocity theorem | |
| = (qm−1 \q) | ||
| = (−1\q) | ||
| = 1 | as q ≡ 1 |
so q is as required.
If m modulo 8 ≡ 1, then (3m−1)/2 is odd. So, by Dirichlet's theorem, there is a prime p and positive integer u where
| p | = 4mu + (3m−1)/2 |
| = ((8u+3)m−1)/2 |
Let q = 8u+3. Then q>0 and
2p = qm − 1 ___ [8].
Then q ≡ 3, modulo 8, and p ≡ 1, modulo 4.
| (−q\p) | = (−1\p)(q\p) | as quadratic residues are multiplicative |
| = (q\p) | as p ≡ 1 | |
| = (p\q) | by the quadratic reciprocity theorem |
| (-1\q) | = -1 | as q ≡ 3 modulo 4 | |
| (2\q) | = -1 | as q ≡ 3 modulo 8 | |
| ⇒ | (-2\q) | = 1 | as quadratic residues are multiplicative |
If m modulo 8 ≡ 3, then (m−1)/2 is odd. So, by Dirichlet's theorem, there is a prime p and positive integer u where
| p | = 4mu + (m−1)/2 |
| = ((8u+1)m−1)/2 |
Let q = 8u+1. Then q>0 and
2p = qm − 1 ___ [8].
Then q ≡ 1, modulo 8, and p ≡ 1, modulo 4.
| (−q\p) | = (−1\p)(q\p) | as quadratic residues are multiplicative |
| = (q\p) | as p ≡ 1 | |
| = (p\q) | by the quadratic reciprocity theorem |
| (-1\q) | = 1 | as q ≡ 1 modulo 4 | |
| (2\q) | = 1 | as q ≡ 1 modulo 8 | |
| ⇒ | (-2\q) | = 1 | as quadratic residues are multiplicative |
If m modulo 8 ≡ 5, then (3m−1)/2 is odd. So, by Dirichlet's theorem, there is a prime p and positive integer u where
| p | = 4mu + (3m−1)/2 |
| = ((8u+3)m−1)/2 |
Let q = 8u+3. Then q>0 and
2p = qm − 1 ___ [8].
Then q ≡ 3, modulo 8, and p ≡ 3, modulo 4.
| (−q\p) | = (−1\p)(q\p) | as quadratic residues are multiplicative |
| = −(q\p) | as p ≡ 3 | |
| = (p\q) | by the quadratic reciprocity theorem, and p ≡ q ≡ 3 |
| (−1\q) | = −1 | as q ≡ 3 modulo 4 | |
| (2\q) | = −1 | as q ≡ 3 modulo 8 | |
| ⇒ | (-2\q) | = 1 | as quadratic residues are multiplicative |
Thus, to summarise, in all the last three cases,
(−q\p)=(p\q) ___ [9]
(−2\q)=1 ___ [10]
Thus:
| (−q\p) | = (p\q) | (by [9]) |
| = (p\q)(−2\q) | (by [10]) | |
| = (−2p\q) | as quadratic residues are multiplicative | |
| = (1−qm\q) | (by [8]) | |
| = (1\q) | ||
| = 1 |
Thus −q is a square modulo p. q is odd, so −q≡12, modulo 2, so (−q\2)=1. Thus
(−q\2p)=1
⇒ (−q\qm−1)=1
i.e. −q is a square modulo qm−1 as required. []
Theorem. 8k+3 is the sum of 3 odd squares.
Proof. By the above theorem, 8k+3 is the sum of 3 squares. Modulo 8, every square ≡ 0, 1 or 4. The only way the sum of 3 squares can ≡ 3 is 1+1+1. []
Theorem (Gauss). Every non-negative integer is the sum of 3 triangular numbers.
Proof. By the above theorem,
8k+3 = (2a+1)2 + (2b+1)2 + (2c+1)2
= 8 T a + 1 + 8 T b + 1 + 8 T c + 1
⇔ k = T a + T b + T c. []
Dr. Math says: