# Express Integer as Sum of Four Squares

This is kind of a follow-up to the question I posted here about expressing integers as the sum of two squares. Is there a similar general method for expressing integers as the sum of four squares? I believe the Lagrange's Four-Square Theorem states that all positive integers are expressible as the sum of four squares of integers, but how do you find these numbers. As an example consider the value $1638$. How can we find the four squares?

• – D.W. Jan 20 '17 at 5:44

Similar to the Brahmagupta-Fibonacci two-square identity. Euler has a four square identity which involves the sum of 4 squares:

$$(a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2) =\\ \quad(a_1b_1 - a_2b_2 - a_3b_3 - a_4b_4)^2 + (a_1b_2+a_2b_1+a_3b_4-a_4b_3)^2 +(a_1b_3 - a_2b_4 + a_3b_1 + a_4b_2)^2 + (a_1b_4 + a_2b_3 - a_3b_2 + a_4b_1)^2$$

Factor $1638$ as products of any small factors you know how to represent as sum of 4 squares. Repeat apply the formula will allow you to represent $1638$ itself as sum of 4 squares.

For example, let's say we have factored $1638$ as $2\cdot 3^2 \cdot 7 \cdot 13$, we have:

\begin{align} & 2\cdot 3^2 \cdot 7 \cdot 13\\ = & (1^2+1^2+0^2+0^2)(1^2+1^2+1^2+0^2)^2(2^2+1^2+1^2+1^2)(3^2+2^2+0^2+0^2)\\ = & (0^2 + 2^2 + 1^2 + 1^2)(1^2+1^2+1^2+0^2)(2^2+1^2+1^2+1^2)(3^2+2^2+0^2+0^2)\\ = & ((-3)^2 + 1^2 + 2^2 + 2^2)(2^2+1^2+1^2+1^2)(3^2+2^2+0^2+0^2)\\ = & ((-11)^2+(-1)^2+2^2 + 0^2)(3^2+2^2+0^2+0^2)\\ = & ((-31)^2 + (-25)^2 + 6^2 + 4^2)\\ \end{align}

This give you a non-trivial representation of $1638$ as $31^2 + 25^2 + 6^2 + 4^2$.

In general, there are many representations of a number as a sum of 4 squares. There is a theorem:

The total number of representations of a positive integer $n$ as the sum of four squares, representations that differ only in order and sign being counted as distinct, is eight times the sum of the divisors of $n$ that are not multiple of $4$.

The above representation is only $1$ out of $8 \sum_{d\mid 1638, 4 \nmid d} d = 34944$ ways of representing $1638$ as sum of 4 squares.

$1638=2\cdot3^2\cdot7\cdot13=(1^2+1^2)3^2(2^2+1^2+1^2+1^2)(3^2+2^2)$ Now use your technique for taking the product of two sums of two squares to a sum of two squares.

Just as the Gaussian integers are a modern method to prove every prime not congruent to $3$ (mod $4$) is a sum of two squares ( since $\mathbb{Z}[i]$ is a Euclidean domain), a similar method works for the so-called Hurwitz quaternions $\mathbb{H} = \{ \frac{a+bi + cj +dk}{2}: a,b,c,d \in \mathbb{Z}, a \equiv b \equiv c \equiv d ({\rm mod} 2) \}$.$\mathbb{H}$ is not a commutative ring, but behaves sufficiently like a Euclidean ring that a similar proof shows that every prime $p$ is a sum of $4$ integer squares. A full proof can be found in I.N. Herstein's "Topics in Algebra", but here is an outline: given any odd prime $p \in \mathbb{N}$, we can express $-1$ as a sum of two squares in $\mathbb{Z}/p\mathbb{Z}$. This means that there are integers $a,b$ such that $p |(a^{2}+b^{2}+1).$ This means that $p$ is not an irreducible element in $\mathbb{H}$, and this leads to the fact that $p = x^{2}+y^{2}+z^{2}+w^{2}$ for integers $x,y,z,w$. Once we know that every prime has such an expression, it follows (as noted in other answers and comments) that every positive integer is a sum of $4$ integer squares. However, it should be noted that, in practice, this may not be the most efficient way to express a given positive integer as a sum of $4$ integer squares.

Hint: Using the same condition as your previous question. If you can express the two numbers which add up to 1638 as a sum of two squares. You are through.:)

This formula seems wrong. Try letting $a_1=b_1$, $a_2=b_2$, $a_3=b_3$, $a_4=a_4$. The result should be $(a_1^2+a_2^2+a_3^2+a_4^2)$.

Euler's four-square identity says that the product of two numbers, each of which is a sum of four squares, is itself a sum of four squares. Specifically:

$$(a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)= (a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4)^2 + (a_1 b_2 - a_2 b_1 + a_3 b_4 - a_4 b_3)^2 + (a_1 b_3 - a_2 b_4 - a_3 b_1 + a_4 b_2)^2 + (a_1 b_4 + a_2 b_3 - a_3 b_2 - a_4 b_1)^2$$