Express $169$ as the sum of $1,2,3,4,5$ non-zero squares

Question

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.

Answer 1

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.

1. $13^2$ gives the expression as one square.

2. 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$.

3. 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$.

4. 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$.

5. 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$.

Answer 2

I posted this in comments, so I might as well document the results. If one has access to Mathematica, then Select[DeleteDuplicates[Sort/@Tuples[Range[13],n]],#.#==169&] lists all ways to write $169$ as a sum of n squares. (This can probably be improved but it works fine for the present purpose.) The results for $n=1,2,3$ are just those found above: $$169=13^2=5^2+12^2=3^2+4^2+12^2$$ For $n=4$ and $n=5$ we respectively obtain {{1,2,8,10},{2,4,7,10},{4,4,4,11},{4,5,8,8},{4,6,6,9}} and {{1,2,2,4,12},{1,2,6,8,8},{1,4,4,6,10},{2,2,2,6,11},{2,2,4,8,9},{2,2,5,6,10},{2,4,6,7,8},{3,4,4,8,8},{5,6,6,6,6}}. These give the representations \begin{align} 169 &=1^2+2^2+8^2+10^2\\ &=2^2+4^2+7^2+10^2\\ &=4^2+4^2+4^2+11^2\\ &=4^2+6^2+6^2+9^2\\ &=1^2+2^2+2^2+4^2+12^2\\ &=1^2+2^2+6^2+8^2+8^2\\ &=1^2+4^2+4^2+6^2+10^2\\ &=2^2+2^2+2^2+6^2+11^2\\ &=2^2+2^2+4^2+8^2+9^2\\ &=2^2+2^2+5^2+6^2+10^2\\ &=2^2+4^2+6^2+7^2+8^2\\ &=3^2+4^2+4^2+8^2+8^2\\ &=5^2+6^2+6^2+6^2+6^2.\\ \end{align} The reader may note the prevalence of solutions with repeated squares. If we require distinct squares, then the code can be simplified to Select[Subsets[Range[13]],#.#==1692&] and produces all such decompositions (regardless of number of terms). In this manner we obtain {{13},{5,12},{3,4,12},{1,2,8,10},{2,4,7,10},{2,4,6,7,8},{1,2,3,5,7,9}}, or

\begin{align} 169 &=13^2\\ &=5^2+12^2\\ &=3^2+4^2+12^2\\ &=1^2+2^2+8^2+10^2\\ &=2^2+4^2+7^2+10^2\\ &=2^2+4^2+6^2+7^2+8^2\\ &=1^2+2^2+3^2+5^2+7^2+9^2. \end{align} Note that there are two decompositions of $169$ into four distinct squares and we've also found a decomposition of $169$ into six distinct squares. (If we allow repeated squares, then the code above produces a total of 20 such decompositions into 6 squares.)