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?
 A: 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.
A: $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.  
A: 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.:) 
