# Find all odd positive integers $n$ for which there exists odd positive integers $x_1,x_2,\ldots,x_n$ such that $x_1^2+x_2^2+\cdots+x_n^2=n^4$.

Find all odd positive integers $$n$$ for which there exists odd positive integers $$x_1,x_2,..,x_n$$ such that $$x_1^2+x_2^2+\cdots+x_n^2=n^4\,.$$

My work so far:

1. For $$n=3$$, the equation $$x_1^2+x_2^2+x_3^2=81$$ has no solutions because if a solution exists the, in modulo $$4$$, we have $$3\equiv 1\pmod{4}$$ which is a contradiction.
1. $$n\ge 5$$?

I need help here.

• Only a remark: if you take $n=m^2$, $m$ odd, then $x_k=m^3$ for all $k$ is a solution. – Kelenner Jun 28 '16 at 14:12
• Is this a contest problem? – almagest Jun 28 '16 at 16:48
• @almagest: Yes. It is the problem of the book "Collection of contest problems 2007-2008" – Roman83 Jun 28 '16 at 16:55
• @Roman83 I have added the tag. This tag is useful for highlighting that the problem is more likely to require thought than knowledge! As I have just discovered to my cost, having spent 5 mins failing to solve it :) – almagest Jun 28 '16 at 17:12

all odd squares are $$1 \pmod 8.$$ This includes $$n^4.$$ Meanwhile, $$x_1^2 +x_2^2+ \cdots+ x_n^2 \equiv n \pmod 8.$$ So it is necessary to have $$n \equiv 1 \pmod 8.$$

In the other direction, all numbers $$k \equiv 3 \pmod 8$$ are the sum of three odd squares. This is a result of Gauss, and equivalent to the fact that all positive integers ae the sum of three triangular numbers, including $$0$$ if needed.

As a result, take any $$n \equiv 1 \pmod 8.$$ Take $$x_4, x_5, \ldots, x_n$$ to be anything (odd) you like, as long as the sum of squares is below $$n^4.$$ The leftover requires $$x_1^2 + x_2^2 + x_3^2 = n^4 - \left( x_4^2 + \cdots+ x_n^2 \right)$$ which can always be solved in (odd) integers.

After Greg's comment, found a fairly greedy solution that does not require quoting Gauss. We have $$n \equiv 1 \pmod 8.$$ Note $$37 \equiv 5 \pmod 8.$$

Let $$K = \frac{3n - 3}{8},$$ $$W = \frac{5n - 37}{8},$$ so that $$K + W = n-5,$$ $$9K + W = 4n-8.$$ The solution will have $$K$$ of the $$x_j$$ equal to $$3,$$ so those squares are $$9,$$ and their sum is $$9K.$$ We will also have $$W$$ of the $$x_j$$ set to $$1,$$ so their sum is just $$W.$$ Then, with a total of $$n$$ (odd) squares, $$\color{red}{ (n^2 - 2)^2 + n^2 + n^2 + n^2 + (n-2)^2 + 9K + W = n^4}$$ With $$n=9$$ we get $$K=3, W=1,$$ $$\; \; 9^4 = 6561,$$ then $$79^2 + 9^2 + 9^2 + 9^2 + 7^2 + 9 \cdot 3 + 1 = 6241 + 81 + 81 + 81 + 49 + 27 + 1 = 6561.$$

With $$n=17$$ we get $$K=6, W=6,$$ $$\; \; 17^4 = 83521,$$ then $$287^2 + 17^2 + 17^2 + 17^2 + 15^2 + 9 \cdot 6 + 6 = 82369 + 289 + 289 + 289 + 225 + 54 + 6 = 83521.$$

With $$n=25$$ we get $$K=9, W=11,$$ $$\; \; 25^4 = 390625,$$ then $$623^2 + 25^2 + 25^2 + 25^2 + 23^2 + 9 \cdot 9 + 11 = 388129 + 625 + 625 + 625 + 529 + 81 + 11 = 390625.$$

With $$n=33$$ we get $$K=12, W=16,$$ $$\; \; 33^4 = 1185921,$$ then $$1087^2 + 33^2 + 33^2 + 33^2 + 31^2 + 9 \cdot 12 + 16 = 1181569 + 1089 + 1089 + 1089 + 961 + 108 + 16 = 1185921.$$

• So for example, take $x_4=\cdots=x_n=1$ and represent $n^4-n+3$ as the sum of three odd squares. – Greg Martin Jun 28 '16 at 17:52
• @GregMartin added in a (mostly) greedy solution at the end that could be found by a student who did not know Gauss's result. – Will Jagy Jun 28 '16 at 18:26