Suppose that $n$ is a sum of squares of three integers divisible by $3$. Prove that it is also a sum of squares of three integers not divisible by $3$.
From the condition, $n=(3a)^2+(3b)^2+(3c)^2=9(a^2+b^2+c^2)$. As long as the three numbers inside are divisible by $3$, we can keep pulling out a factor of $9$, until we get $n=9^k(x^2+y^2+z^2)$. Modulo $3$, squares leave a remainder of either $0$ or $1$. Therefore one or three of $x,y,z$ are divisible by $3$.
Best Answer
Let $n=(3x_1)^2+(3x_2)^2+(3x_3)^2$. Then
$$n=(2x_1+2x_2-x_3)^2+(2x_2+2x_3-x_1)^2+(2x_3+2x_1-x_2)^2\;,$$
and the $x_i$ can independently be chosen with either sign.
Let $k$ be the lowest exponent of $3$ in the $x_i$, and write $x_i=3^k(3a_i+r_i)$ with $0\le r_i\lt3$. By construction, at least one of the $r_i$ is non-zero. If only one is non-zero, all sums contain exactly $k$ factors of $3$. If two are non-zero, choose the signs so that $r=(0,1,1)$, and if all three are nonzero, choose the signs so that $r=(1,1,2)$. In all cases, all three sums contain exactly $k$ factors of $3$, and thus at least one less than before. The result then follows by induction.