I'm trying to solve the following exercise.
Show that $169$ can be expressed as a sum of $1,2,3,4,5$ non-zero squares, and deduce that any $n \ge 169$ is the sum of five non-zero squares.
The latter part of the exercise is clear from Lagrange's four squares theorem, namely that every integer can be expressed as the sum of four integers. (There's also an answer Integers which are the sum of non-zero squares, detailing the exact steps.) I'm having trouble with the first part of the exercise.
For expressing $169$ as a sum of one square, we have $169=13^2$. Now, $13 = 2^2 + 3^2$, so we can use the identity $(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2$ to get $13^2 = (6+6)^2 + (2^2-3^2)^2$. But what about the rest? Is there any way of obtaining $169$ as a sum of $3,4,5$ non-zero squares, except by brute force, perhaps? (Brute force answers are also welcome, especially if they employ intuition or clever tricks! I will upvote them too)
There is one numerical answer to this in the link above, but I'm looking for intuition or a systematic way of doing things, not just a number solution expressing $169$ as a sum of non-zero squares.
Best Answer
I wondered how long this would take me, so I sat down to do it and here was my process.
I thought I would have to do some quick comparisons, so I first wrote the squares from $1$ to $169$ at the top of a sheet of paper. I had expected to repeatedly try a greedy algorithm of taking one large square and seeing what one can do with the remaining small number, but in fact this was only necessary once.
$13^2$ gives the expression as one square.
This amounts to choosing two squares and adding them up. In principle I could have looked at my list of squares and begun to compare, but I think it's pretty common to recognize the Pythagorean triple $5^2 + 12^2 = 13^2$.
For $3$, I think it's easiest to modify the previous triple by re-expressing $5$ in its own Pythagorean triple to get $(3^2 + 4^2) + 12^2 = 13^2$.
Although I'm listing these in order, I actually did $4$ squares last. I didn't do anything clever.
Instead I proceeded greedily: begin with $169$, subtract a large square and see if what remains was obviously a sum of $3$ squares. $25$ is not a sum of three squares, so the initial try of representing $169 - 12^2 = 5^2$ as a sum of three squares doesn't work. But the second guess leads to $169 - 11^2 = 48 = 4^4 + 4^4 + 4^2$ does work. Thus $4^2 + 4^2 + 4^2 + 11^2$ works for $4$.
I know the theorem that every number can be written as a sum of $4$ squares, so you can't really go too wrong here. I thought to examine again the basic Pythagorean triple $5^2 + 12^2 = 13^2$ and to rewrite $5^2$ as a sum of $4$ squares. This can be done with $1^2 + 2^2 + 2^2 + 4^2$ (and all these numbers are small enough to quickly get this with no real work), giving the set $1^2 + 2^2 + 2^2 + 4^2 + 12^2$.