Unit 8: Representation of Integers as Sums of Squares

1. The Two-Square Problem

The problem of representing integers as sums of two squares traces back to Diophantus of Alexandria, but the first definitive modern breakthrough was announced by Pierre de Fermat in a famous letter to Father Marin Mersenne dated December 25, 1640 (hence the name Fermat's Christmas Theorem).

Fundamental Question: Which positive integers $n \in \mathbb{N}$ can be represented as the sum of two integer squares:

Before resolving the general question, we examine the behavior of prime numbers.

2. Parity and Quadratic Residue Obstruction

Lemma 8.1 (Modulo 4 Obstruction): Let $x \in \mathbb{Z}$. Then:

Consequently, for any $x, y \in \mathbb{Z}$:

In particular, no integer $n \equiv 3 \pmod 4$ can ever be represented as the sum of two squares.

Proof: If $x = 2k$, $x^2 = 4k^2 \equiv 0 \pmod 4$. If $x = 2k+1$, $x^2 = 4(k^2 + k) + 1 \equiv 1 \pmod 4$. Taking all four combinations of $x^2, y^2 \in \{0, 1\} \pmod 4$:

• $0 + 0 = 0 \pmod 4$
• $0 + 1 = 1 \pmod 4$
• $1 + 0 = 1 \pmod 4$
• $1 + 1 = 2 \pmod 4$

The residue $3 \pmod 4$ is completely unattainable. $\blacksquare$

For prime numbers $p$:

• If $p = 2$: $2 = 1^2 + 1^2$ is a sum of two squares.
• If $p$ is an odd prime and $p = x^2 + y^2$, then since $p$ is odd, one of $x, y$ is even and the other is odd, so $p \equiv 0 + 1 = 1 \pmod 4$.

Thus, a necessary condition for an odd prime $p$ to be a sum of two squares is:

3. Fermat's Two-Square Theorem

Fermat claimed, and Leonhard Euler proved in 1749 (after 7 years of effort), that this necessary condition is also sufficient!

Theorem 8.1 (Fermat's Christmas Theorem): An odd prime number $p$ can be expressed as the sum of two integer squares:

if and only if:

Furthermore, this representation is unique up to the order of the summands and signs of $x$ and $y$.

4. Quadratic Residues: The Root of $-1$ Modulo $p$

The central algebraic lever underlying all proofs of Fermat's theorem is the existence of an integer whose square is congruent to $-1$ modulo $p$.

Lemma 8.2 (Square Root of $-1$): Let $p$ be an odd prime. The congruence:

has an integer solution $z \in \mathbb{Z}$ if and only if $p \equiv 1 \pmod 4$. An explicit solution is given by:

Proof: By Euler's Criterion for quadratic residues:

• If $p \equiv 1 \pmod 4$, then $\frac{p-1}{2} = 2k$ is even, so $(-1)^{\frac{p-1}{2}} = 1$. Hence $-1$ is a quadratic residue modulo $p$.
• If $p \equiv 3 \pmod 4$, then $\frac{p-1}{2} = 2k+1$ is odd, so $(-1)^{\frac{p-1}{2}} = -1$. Hence $-1$ is a quadratic non-residue modulo $p$.

To obtain the explicit formula, by Wilson's Theorem $(p-1)! \equiv -1 \pmod p$. Grouping the product $(p-1)! = 1 \cdot 2 \cdots \left(\frac{p-1}{2}\right) \cdot \left(\frac{p+1}{2}\right) \cdots (p-1)$: Notice that for $1 \le j \le \frac{p-1}{2}$:

Thus:

For $p \equiv 1 \pmod 4$, $(-1)^{(p-1)/2} = 1$, giving:

Letting $z = \left(\frac{p-1}{2}\right)!$, we have $z^2 \equiv -1 \pmod p$. $\blacksquare$

5. Thue's Lemma: The Pigeonhole Bridge to Squares

In 1902, Axel Thue gave an ingenious proof using the Dirichlet Pigeonhole Principle that bridges modular congruences to Diophantine equations.

Lemma 8.3 (Thue's Lemma): Let $n > 1$ and let $a \in \mathbb{Z}$ with $\gcd(a, n) = 1$. Then there exist integers $x, y$ such that:

Proof: Let $k = \lfloor \sqrt{n} \rfloor$. Then $k < \sqrt{n} < k+1$, which means $(k+1)^2 > n$. Consider the set of pairs:

The total number of pairs in $S$ is $|S| = (k+1)^2 > n$. To each pair $(u, v) \in S$, associate the residue:

Since there are $(k+1)^2 > n$ pairs and only $n$ possible residues modulo $n$, by the Pigeonhole Principle, there exist two distinct pairs $(u_1, v_1) \ne (u_2, v_2) \in S$ such that:

Set $x = u_1 - u_2$ and $y = v_1 - v_2$.

• Since $(u_1, v_1) \ne (u_2, v_2)$, $(x, y) \ne (0, 0)$.
• Since $0 \le u_1, u_2 \le k$, we have $-k \le x \le k$, so $|x| \le k < \sqrt{n}$.
• Similarly, $|y| \le k < \sqrt{n}$.
• If $x = 0$, then $y \equiv a(0) = 0 \pmod n$, and since $|y| < \sqrt{n} < n$, this forces $y = 0$, contradicting $(x, y) \ne (0, 0)$. Thus $x \ne 0$.
• Similarly, if $y = 0$, then $a x \equiv 0 \pmod n \implies n \mid x$ (since $\gcd(a, n) = 1$), which contradicts $0 < |x| < n$. Thus $y \ne 0$.

Hence $0 < |x| < \sqrt{n}$ and $0 < |y| < \sqrt{n}$. $\blacksquare$

6. Rigorous Proof of Fermat's Theorem via Thue's Lemma

Proof of Theorem 8.1: Let $p$ be a prime with $p \equiv 1 \pmod 4$. By Lemma 8.2, there exists $z \in \mathbb{Z}$ such that $z^2 \equiv -1 \pmod p$. Applying Thue's Lemma (Lemma 8.3) with $n = p$ and $a = z$: There exist integers $x, y$ such that:

Squaring both sides of the congruence:

Substituting $z^2 \equiv -1 \pmod p$:

Thus, $p \mid (x^2 + y^2)$.

Now evaluate the size of $x^2 + y^2$: Since $0 < |x| < \sqrt{p}$ and $0 < |y| < \sqrt{p}$:

Since $x^2 + y^2$ is a positive integer multiple of $p$ strictly between $0$ and $2p$, the only possible multiple is $1 \cdot p$!

This completes the existence proof. $\blacksquare$

1. The Ring of Gaussian Integers

A profound algebraic perspective on sums of two squares was opened by Carl Friedrich Gauss in 1828–1832 with the introduction of Gaussian integers.

Definition 8.1 (Gaussian Integers): The ring of Gaussian integers, denoted $\mathbb{Z}[i]$, is the subring of the complex numbers $\mathbb{C}$ defined by:

Addition and multiplication follow the standard field operations of $\mathbb{C}$:

Geometrically, $\mathbb{Z}[i]$ is the square lattice of points with integer coordinates in the complex plane $\mathbb{C} \cong \mathbb{R}^2$.

2. The Field Norm

Definition 8.2 (Field Norm): For $\alpha = a + b i \in \mathbb{Z}[i]$, the norm $N(\alpha)$ is the squared modulus:

where $\bar{\alpha} = a - b i$ is the complex conjugate.

Proposition 8.1 (Properties of the Norm):

1. Non-negativity: $N(\alpha) \ge 0$ for all $\alpha \in \mathbb{Z}[i]$, with $N(\alpha) = 0 \iff \alpha = 0$.
2. Multiplicativity: For all $\alpha, \beta \in \mathbb{Z}[i]$:

1. Integer Values: $N(\alpha) \in \mathbb{Z}_{\ge 0}$.

Proof of Multiplicativity:

3. Units in $\mathbb{Z}[i]$

Proposition 8.2 (Units): An element $u \in \mathbb{Z}[i]$ is invertible (a unit) if and only if $N(u) = 1$. The group of units $\mathbb{Z}[i]^\times$ is cyclic of order $4$:

Proof: If $u$ is a unit, there exists $v \in \mathbb{Z}[i]$ such that $u v = 1$. Taking norms: $N(u) N(v) = N(1) = 1$. Since $N(u), N(v) \in \mathbb{Z}_{\ge 0}$, we must have $N(u) = 1$. Conversely, if $u = a + b i$ and $N(u) = a^2 + b^2 = 1$, then since $a, b \in \mathbb{Z}$: Either $a = \pm 1, b = 0$ (giving $\pm 1$) or $a = 0, b = \pm 1$ (giving $\pm i$). In all four cases, $u$ has an inverse in $\mathbb{Z}[i]$. $\blacksquare$

4. Euclidean Division Algorithm in $\mathbb{Z}[i]$

The ring $\mathbb{Z}[i]$ shares the fundamental Euclidean division property with $\mathbb{Z}$.

Theorem 8.2 (Division Algorithm for Gaussian Integers): Given $\alpha, \beta \in \mathbb{Z}[i]$ with $\beta \ne 0$, there exist $q, r \in \mathbb{Z}[i]$ such that:

Proof: Consider the quotient in the field of fractions $\mathbb{Q}(i) \subset \mathbb{C}$:

Choose integers $u, v \in \mathbb{Z}$ that are closest to the rational numbers $x, y$:

Set $q = u + v i \in \mathbb{Z}[i]$ and define the remainder $r = \alpha - \beta q \in \mathbb{Z}[i]$. Then:

Taking the norm of both sides:

Multiplying through by $N(\beta) > 0$:

Corollary 8.1 (UFD Property): Because $\mathbb{Z}[i]$ is a Euclidean Domain (ED), it is a Principal Ideal Domain (PID), and therefore a Unique Factorization Domain (UFD). Every nonzero, non-unit Gaussian integer factors uniquely into a product of irreducible Gaussian primes, up to multiplication by units $\{\pm 1, \pm i\}$.

5. Classification of Gaussian Primes

Which elements in $\mathbb{Z}[i]$ are prime? A rational prime $p \in \mathbb{Z}$ behaves in one of three ways inside $\mathbb{Z}[i]$:

Theorem 8.3 (Classification of Gaussian Primes): Up to unit associates, the primes of $\mathbb{Z}[i]$ are precisely:

1. Ramified Prime:

The element $1 + i$ is a Gaussian prime of norm $N(1 + i) = 1^2 + 1^2 = 2$.

1. Inert Primes:

Every rational prime $q \equiv 3 \pmod 4$ remains prime (inert) in $\mathbb{Z}[i]$, with norm $N(q) = q^2$.

1. Split Primes:

Every rational prime $p \equiv 1 \pmod 4$ splits into two non-associate conjugate Gaussian primes:

where $N(\pi) = N(\bar{\pi}) = a^2 + b^2 = p$.

Direct Proof of Split Behavior: Let $p$ be a prime with $p \equiv 1 \pmod 4$. As proved in Lemma 8.2, there exists $z \in \mathbb{Z}$ such that $z^2 \equiv -1 \pmod p$. This means $p \mid (z^2 + 1)$ in $\mathbb{Z}$. In $\mathbb{Z}[i]$, we can factor:

Thus $p \mid (z + i)(z - i)$ in $\mathbb{Z}[i]$.

Now, suppose for a contradiction that $p$ were prime (irreducible) in $\mathbb{Z}[i]$. By Euclid's Lemma in the UFD $\mathbb{Z}[i]$, $p$ must divide either $z + i$ or $z - i$. But if $p \mid (z + i)$, then there exists $c + d i \in \mathbb{Z}[i]$ such that:

Since $p \ge 5$ and $d \in \mathbb{Z}$, $p d = 1$ has no integer solution! Hence $p$ does NOT divide $z + i$, and by the same argument $p \nmid (z - i)$.

Therefore, $p$ is not prime in $\mathbb{Z}[i]$! Since $p$ is reducible and not a unit, it factors as:

where $\pi, \beta \in \mathbb{Z}[i]$ are neither units. Taking norms:

Since $\pi, \beta$ are not units, $N(\pi) > 1$ and $N(\beta) > 1$. Since $p$ is a rational prime, the only integer factorization of $p^2$ into factors $> 1$ is:

Writing $\pi = a + b i$, we immediately obtain:

This gives an exceptionally beautiful, purely ring-theoretic proof of Fermat's Christmas Theorem! $\blacksquare$

1. The Brahmagupta-Fibonacci Identity

How do sums of two squares behave under multiplication?

Identity 8.1 (Brahmagupta-Fibonacci Identity): For any real or complex numbers $a, b, c, d$:

Proof: In the Gaussian integers, let $\alpha = a + b i$ and $\beta = c + d i$. The multiplicativity of the norm states:

Expanding both sides:

The second variant follows by replacing $\beta$ with $\bar{\beta} = c - d i$, since $N(\bar{\beta}) = N(\beta)$. $\blacksquare$

The identity proves that the set of integers representable as sums of two squares is closed under multiplication.

2. Complete Classification of Two-Square Integers

Theorem 8.4 (Two-Square Characterization): A positive integer $n \in \mathbb{N}$ can be expressed as the sum of two squares:

if and only if in the canonical prime factorization of $n$:

every prime factor $q_k \equiv 3 \pmod 4$ appears with an even exponent (i.e., $b_k \equiv 0 \pmod 2$ for all $k$).

Proof: Sufficiency ($\Leftarrow$): Suppose each $b_k = 2 c_k$. Then:

• $2 = 1^2 + 1^2$ is a sum of two squares.
• Each prime $p_j \equiv 1 \pmod 4$ is a sum of two squares by Fermat's Theorem (Theorem 8.1).
• By Identity 8.1, the product of sums of two squares is again a sum of two squares.

Thus $2^{a_0} \prod p_j^{a_j} = u^2 + v^2$.

• Multiplying by the perfect square $M^2 = \left( \prod q_k^{c_k} \right)^2$:

which is a sum of two squares.

Necessity ($\Rightarrow$): Suppose $n = x^2 + y^2$. Let $q$ be any prime divisor of $n$ with $q \equiv 3 \pmod 4$. We must prove that the exact power of $q$ dividing $n$, denoted $v_q(n)$, is even.

Let $g = \gcd(x, y)$, and write $x = g x_1, y = g y_1$ with $\gcd(x_1, y_1) = 1$. Then:

Suppose for contradiction that $q \mid (x_1^2 + y_1^2)$. Then $x_1^2 + y_1^2 \equiv 0 \pmod q \implies x_1^2 \equiv -y_1^2 \pmod q$. If $q \mid y_1$, then $q \mid x_1^2 \implies q \mid x_1$, contradicting $\gcd(x_1, y_1) = 1$. Thus $q \nmid y_1$, so $y_1$ has a modular inverse $y_1^{-1}$ modulo $q$. Multiplying by $(y_1^{-1})^2$:

This implies that $-1$ is a quadratic residue modulo $q$, so $\left(\frac{-1}{q}\right) = 1$. But by Lemma 8.2, for $q \equiv 3 \pmod 4$:

This contradiction proves that $q \nmid (x_1^2 + y_1^2)$! Therefore, all factors of $q$ in $n$ must come from $g^2$:

Hence, every prime factor $q \equiv 3 \pmod 4$ appears with an even exponent. $\blacksquare$

3. Number of Representations: Jacobi's Two-Square Formula

How many integer pairs $(x, y) \in \mathbb{Z}^2$ satisfy $x^2 + y^2 = n$?

Definition 8.3 (Representation Function $r_2(n)$):

Note that order matters ($(x, y) \ne (y, x)$ if $x \ne y$) and signs matter ($(\pm x, \pm y)$).

Theorem 8.5 (Jacobi's Two-Square Formula): Let $d_1(n)$ denote the number of divisors of $n$ congruent to $1 \pmod 4$, and $d_3(n)$ denote the number of divisors congruent to $3 \pmod 4$:

Then:

where $\chi_4$ is the non-principal Dirichlet character modulo 4:

Proof: Finding pairs $(x, y) \in \mathbb{Z}^2$ with $x^2 + y^2 = n$ is identical to finding Gaussian integers $\alpha = x + i y \in \mathbb{Z}[i]$ with $N(\alpha) = n$. Factor $n$ in $\mathbb{Z}$:

In $\mathbb{Z}[i]$:

• $2 = -i (1 + i)^2$, with $N(1 + i) = 2$.
• Each $p_j = \pi_j \bar{\pi}_j$, with $N(\pi_j) = N(\bar{\pi}_j) = p_j$.
• Each $q_k$ is inert, with $N(q_k) = q_k^2$.

Any Gaussian integer $\alpha$ with $N(\alpha) = n$ must have prime factorization:

where $u \in \{1, -1, i, -i\}$ is one of the $4$ units.

• If any $b_k$ is odd, no such $\alpha$ exists, so $r_2(n) = 0$.
• For each $p_j$, the power $c_j$ can be chosen in $a_j + 1$ ways: $c_j \in \{0, 1, \dots, a_j\}$.
• There are $4$ choices for the unit $u$.

Thus:

On the other hand, the arithmetic function $f(n) = d_1(n) - d_3(n) = (\chi_4 * \mathbf{1})(n)$ is multiplicative! Evaluating $f$ on prime powers:

• $f(2^a) = \chi_4(1) + \chi_4(2) + \dots + \chi_4(2^a) = 1 + 0 + \dots = 1$.
• For $p \equiv 1 \pmod 4$: $f(p^a) = \sum_{m=0}^a \chi_4(p^m) = \sum_{m=0}^a 1 = a + 1$.
• For $q \equiv 3 \pmod 4$: $f(q^b) = \sum_{m=0}^b \chi_4(q^m) = 1 - 1 + 1 - 1 + \dots = \begin{cases} 1 & \text{if } b \text{ is even} \\ 0 & \text{if } b \text{ is odd} \end{cases}$

Multiplying over all prime factors, $4 f(n)$ matches $r_2(n)$ exactly on all positive integers! $\blacksquare$

4. Geometric Interpretation: The Gauss Circle Problem

The value $r_2(n)$ represents the number of integer lattice points on the circle of radius $\sqrt{n}$ centered at the origin:

The total number of lattice points inside and on the closed disk of radius $R$ is:

Since each lattice point corresponds to a unit square of area $1$, the number of points approximates the area of the disk:

Gauss proved the elementary bound for the error term:

The problem of determining the infimum exponent $\theta$ such that $E(R) = \mathcal{O}(R^{\theta})$ is the celebrated Gauss Circle Problem (conjectured to be $\theta = 1/2 + \varepsilon$).

1. Beyond Two Squares

While not every integer is a sum of two squares (e.g., $3, 6, 7, 11, 12, 14, 15$), and not every integer is a sum of three squares (e.g., $7, 15, 23, 28$), Leonhard Euler suspected that four squares suffice for every integer.

The linchpin of Euler's attack was discovered in 1748: a 4-variable analogue of the Brahmagupta-Fibonacci identity.

2. Euler's Four-Square Identity

Theorem 8.6 (Euler's Four-Square Identity): For any real or complex numbers $a_1, a_2, a_3, a_4$ and $b_1, b_2, b_3, b_4$:

where:

While verifying this algebraic identity by brute-force expansion involves 16 products of squares and 24 cross-terms that cancel in pairs, the true structural origin of the identity remained mysterious for nearly a century until William Rowan Hamilton discovered the quaternions in 1843.

3. The Algebra of Quaternions $\mathbb{H}$

Definition 8.4 (Hamilton Quaternions): The quaternion algebra $\mathbb{H}$ is the 4-dimensional associative division algebra over $\mathbb{R}$ with basis $\{1, i, j, k\}$ satisfying the fundamental relations:

from which it follows that:

Any quaternion $q \in \mathbb{H}$ is written as:

Multiplication in $\mathbb{H}$ is non-commutative ($i j \ne j i$).

4. Quaternion Conjugation and Norm

Definition 8.5 (Quaternion Conjugate and Norm): For $q = a_1 + a_2 i + a_3 j + a_4 k \in \mathbb{H}$, the quaternion conjugate is:

The quaternion norm is defined by:

Theorem 8.7 (Multiplicativity of Quaternion Norm): For any two quaternions $p, q \in \mathbb{H}$:

and consequently:

Proof: To verify anti-automorphism $\overline{p q} = \bar{q} \bar{p}$, check on basis elements:

• $\overline{i j} = \bar{k} = -k$. Meanwhile $\bar{j} \bar{i} = (-j)(-i) = j i = -k$. Matches!
• The linearity over $\mathbb{R}$ extends this to all $p, q \in \mathbb{H}$.

Now evaluate the squared norm:

By associativity of quaternion multiplication:

Since $\|q\|^2 \in \mathbb{R}$ is a real scalar, it commutes with all elements of $\mathbb{H}$:

Remark (Euler's Identity as Quaternion Norm): Let $p = a_1 + a_2 i + a_3 j + a_4 k$ and $q = b_1 + b_2 i + b_3 j + b_4 k$. Direct computation of the product $p q$ gives:

where $c_1, c_2, c_3, c_4$ are precisely the expressions in Theorem 8.6! Since $\|p q\|^2 = c_1^2 + c_2^2 + c_3^2 + c_4^2$ and $\|p\|^2 \|q\|^2 = (a_1^2 + a_2^2 + a_3^2 + a_4^2)(b_1^2 + b_2^2 + b_3^2 + b_4^2)$, the multiplicativity of the quaternion norm proves Euler's four-square identity in a single stroke!

5. Hurwitz Integers and Maximal Orders

In 1896, Adolf Hurwitz discovered that to develop a Euclidean division algorithm for quaternions, the naive ring $\mathbb{Z}[i, j, k]$ is insufficient (its lattice points are too sparse to guarantee remainders of norm $< 1$). Instead, one must include the body-centered points:

Definition 8.6 (Hurwitz Quaternions): The ring of Hurwitz quaternions $\mathcal{H}$ is:

The ring $\mathcal{H}$ has exactly $24$ units (the binary tetrahedral group):

and satisfies a left- and right-Euclidean division algorithm.

1. Lagrange's Four-Square Theorem

In 1770, Joseph-Louis Lagrange proved what Fermat had claimed more than a century earlier: every positive integer is the sum of at most four squares.

Theorem 8.8 (Lagrange's Four-Square Theorem): Every positive integer $n \in \mathbb{N}$ can be expressed as the sum of four integer squares:

2. Line-by-Line Proof of Lagrange's Theorem

Thanks to Euler's identity (Theorem 8.6), the product of any two sums of four squares is another sum of four squares. Since every integer $n > 1$ factors into prime numbers, it suffices to prove the theorem for prime numbers $p$.

• For $p = 2$: $2 = 1^2 + 1^2 + 0^2 + 0^2$.
• Hence, let $p$ be an odd prime. The proof proceeds in two steps:

1. Solvability of a Congruence: Show that there exists a multiple $m p$ with $1 \le m < p$ that is a sum of four squares.

2. Method of Infinite Descent: Show that if $m p = x_1^2 + x_2^2 + x_3^2 + x_4^2$ with $m > 1$, we can construct a smaller multiple $m' p = y_1^2 + y_2^2 + y_3^2 + y_4^2$ with $1 \le m' < m$.

Step 1: The Pigeonhole Lemma

Lemma 8.4 (Modular Solvability): For any odd prime $p$, there exist integers $x, y$ such that:

Consequently, there exists an integer $m$ with $1 \le m < p$ such that:

Proof: Consider the two sets of residue classes modulo $p$:

• In $S_1$, all elements are distinct: if $x_1^2 \equiv x_2^2 \pmod p$, then $p \mid (x_1 - x_2)(x_1 + x_2)$.

Since $0 \le x_1, x_2 \le \frac{p-1}{2}$, we have $|x_1 - x_2| < p$ and $0 \le x_1 + x_2 \le p-1 < p$. Thus $x_1 = x_2$. Hence $|S_1| = \frac{p-1}{2} + 1 = \frac{p+1}{2}$.

• By the identical reasoning, all elements in $S_2$ are distinct, so $|S_2| = \frac{p+1}{2}$.

Now sum their cardinalities:

Since there are only $p$ distinct residue classes modulo $p$, by the Pigeonhole Principle, $S_1$ and $S_2$ must have at least one residue in common! That is, there exist $0 \le x, y \le \frac{p-1}{2}$ such that:

Therefore, $x^2 + y^2 + 1^2 + 0^2 = m p$ for some integer $m \ge 1$. Moreover:

Dividing by $p$, we obtain $m < p$. $\blacksquare$

Step 2: Minimal Descent on the Multiplier $m$

Proof of Descent (Step 2): By Step 1, the set of integers $m \in \{1, 2, \dots, p-1\}$ such that $m p$ is a sum of four squares is non-empty. By the Well-Ordering Principle of $\mathbb{N}$, there exists a minimal such integer $m$. We claim that $m = 1$.

Suppose for contradiction that $m > 1$. Let $m p = x_1^2 + x_2^2 + x_3^2 + x_4^2$.

Case A: $m$ is even. If $m$ is even, then $m p$ is even. Thus $x_1^2 + x_2^2 + x_3^2 + x_4^2 \equiv 0 \pmod 2$. This means either:

1. All four $x_j$ are of the same parity (all even or all odd), or
2. Exactly two are even and two are odd.

In either case, we can pair them up, say $(x_1, x_2)$ and $(x_3, x_4)$, such that $x_1 \equiv x_2 \pmod 2$ and $x_3 \equiv x_4 \pmod 2$. Then $\frac{x_1 \pm x_2}{2}$ and $\frac{x_3 \pm x_4}{2}$ are all integers. Observe the algebraic identity:

Setting $m' = m/2 < m$, we have expressed $m' p$ as a sum of four integer squares, contradicting the minimality of $m$!

Case B: $m$ is odd and $m > 1$. For each $j \in \{1, 2, 3, 4\}$, choose $y_j \in \mathbb{Z}$ such that:

Then:

Thus:

for some integer $k \ge 0$.

• Could $k = 0$? If $k = 0$, then each $y_j = 0$, which means $x_j \equiv 0 \pmod m$.

Then $m \mid x_j$ for all $j$, so $m^2 \mid \sum x_j^2 = m p \implies m \mid p$. Since $p$ is prime and $1 < m < p$, this is impossible! Thus $k > 0$.

• How large can $k$ be?

Dividing by $m$: $k < m$.

Now multiply $(m p)$ and $(k m)$ using Euler's Four-Square Identity (Theorem 8.6):

where:

Modulo $m$, since $y_j \equiv x_j \pmod m$:

Thus, every $z_j$ is divisible by $m$! Dividing both sides of $m^2 (k p) = \sum z_j^2$ by $m^2$:

Since each $z_j / m \in \mathbb{Z}$, we have represented $k p$ as a sum of four integer squares with $1 \le k < m$. This contradicts the minimality of $m$!

Therefore, $m = 1$, and $p = x_1^2 + x_2^2 + x_3^2 + x_4^2$. $\blacksquare$

3. Number of Representations: Jacobi's Four-Square Theorem

In 1834, Carl Gustav Jacob Jacobi derived the exact formula for $r_4(n) = \#\{(x_1, x_2, x_3, x_4) \in \mathbb{Z}^4 : \sum x_j^2 = n\}$ using theta functions.

Theorem 8.9 (Jacobi's Four-Square Formula): For every positive integer $n \in \mathbb{N}$:

Since $1 \mid n$ and $4 \nmid 1$, the sum is always at least $8 \cdot 1 = 8 > 0$, giving an independent proof that $r_4(n) \ge 8$ for all $n \ge 1$.

4. Legendre's Three-Square Theorem

Which integers can be written as the sum of three squares?

Theorem 8.10 (Legendre's Three-Square Theorem, 1798): A positive integer $n$ can be expressed as the sum of three integer squares:

if and only if $n$ is not of the form:

Proof of Necessity ($\Rightarrow$): For any integer $w$, $w^2 \equiv 0, 1, \text{ or } 4 \pmod 8$. The possible sums of three squares modulo $8$ are:

• $0+0+0 = 0$
• $0+0+1 = 1$
• $0+1+1 = 2$
• $1+1+1 = 3$
• $0+0+4 = 4$
• $0+1+4 = 5$
• $1+1+4 = 6$

The residues $7 \pmod 8$ is completely missing! Thus, no integer $n \equiv 7 \pmod 8$ can be a sum of three squares.

Now suppose $n = 4^a (8 b + 7) = x^2 + y^2 + z^2$ for some $a \ge 1$. Modulo $4$:

Since squares modulo 4 are 0 or 1, the only way their sum can be $0 \pmod 4$ is if all three are $0 \pmod 4$:

Dividing by 4:

By induction on $a$, descending $a$ times yields:

which is impossible because $8b+7 \equiv 7 \pmod 8$ is not a sum of three squares! This proves necessity. $\blacksquare$

Remark on Sufficiency: Proving that every integer not of the form $4^a(8b+7)$ is indeed a sum of three squares is notoriously difficult; Adrien-Marie Legendre published an incomplete proof in 1798, and Carl Friedrich Gauss gave the first complete proof in 1801 (Disquisitiones Arithmeticae, Art. 291) using his deep theory of ternary quadratic forms.

5. Hierarchy of Sums of Squares

| Number of Squares | Solvability Condition | Representation Count Formula | | :--- | :--- | :--- | | Two Squares ($x^2 + y^2$) | All prime factors $q \equiv 3 \pmod 4$ have even powers | $r_2(n) = 4(d_1(n) - d_3(n))$ | | Three Squares ($x^2 + y^2 + z^2$) | $n \ne 4^a(8b + 7)$ | Proportional to class numbers of binary quadratic forms | | Four Squares ($x_1^2 + x_2^2 + x_3^2 + x_4^2$) | All integers $n \ge 0$ (Unconditional!) | $r_4(n) = 8 \sum_{d \mid n, 4 \nmid d} d$ |