Find all $x,y,z$ such that $x^2 + y^2 + z^2 = 3^{10}$ By Legendre's 3-squares theorem, a number $n = x^2 + y^2 + z^2$ can be written as the sum of three squares if $n \neq 4^a(8b+7)$.  In my case, I am choosing $$n = 3^{10} \equiv (3^2)^5 \equiv 1 \mod 8$$
which is safe.  In that case, is there any way I can find these integers by induction?  Perhaps I can try:
$$ 3 = 1^2 + 1^2 + 1^2 $$
This is encouraging to let's try the case of $n=9$:  That is even easier since it is a perfect square:
$$ 9 = 3^2 + 0^2 + 0^2 $$
Let's take it one step further.  $n = 3^3 = 27$.  There is no way to combine my previous two answers to get a third solution.  However, by searching:
$$ 27 = 5^2 + 1^2 + 1^2  = 3^2 + 3^2 + 3^2$$
and $n = 81 = 3^4$ is another perfect square (in fact a perfect 4th power) but there may be other solutions:
$$ 81 = 9^2 + 0^2 + 0^2 = \dots $$
Is it possible to get all the way to $n = 3^{10}$ in this manner.  Is there an inductive approach to solving:
$$ 3^n = x^2 + y^2 + z^2 $$
for all odd and even powers $n$ ?
 A: Proffering a special solution in your case of $3^n$ using quaternion algebra.
When $n$ is odd this is trivial.
When $n$ is even we can consider the quaternion
$$
q=2+2i+j.
$$
It has reduced norm $N(q)=2^2+2^2+1^2=9$, so we know that $N(q^\ell)=9^\ell$
for all integers $\ell$. Also, clearly the powers of $q$ belong to the Lipschitz order $\mathcal O_L=\Bbb{Z}\oplus\Bbb{Z}i\oplus \Bbb{Z}j\oplus\Bbb{Z}k.$
Let $u$ be the unit vector $u=(2i+j)/\sqrt5$. Because $u^2=-1$ (holds for all unit vectors $u$), it follows that  $\Bbb{C}_u:=\Bbb{R}\oplus \Bbb{R}u$ is a subring of the quaternions (actually it is isomorphic to the field of complex numbers, but we won't be needing that bit). Consequently $q^\ell\in\Bbb{C}_u$ for all integers $\ell$.
Therefore:


*

*The quaternion $q^\ell$ has integer coefficients, because those powers belong to the ring $\mathcal{O}_L$.

*When we write the quaternion power $$q^\ell=a_\ell+b_\ell i+c_\ell j+d_\ell k$$ with some integers $a_\ell,b_\ell, c_\ell, d_\ell$, we always have $d_\ell=0$, because $q^\ell\in\Bbb{C}_u$.

*Thus $$9^\ell=a_\ell^2+b_\ell^2+c_\ell^2$$ is a presentation of $9^\ell$ as a sum of three integers for all natural numbers $\ell$.


So we get
$$
\begin{array}{c|c|c|c}
\ell&a_\ell&b_\ell&c_\ell\\
\hline
1&2&2&1\\
2&-1&8&4\\
3&-22&14&7\\
4&-79&-16&-8\\
5&-118&-190&-95\\
6&239&-616&-308\\
7&2018&-754&-377
\end{array}
$$
Extend as you see fit.

The quaternion product rule of $q^{\ell+1}=q\cdot q^\ell$ translates to the following recurrence formula for the integers $a_\ell,b_\ell,c_\ell$:


*

*$a_{\ell+1}=2a_{\ell}-2b_{\ell}-c_{\ell}$,

*$b_{\ell+1}=2a_{\ell}+2b_{\ell}$,

*$c_{\ell+1}=2c_{\ell}+a_{\ell}$,

*And, as an extra, we shall always have $0=d_{\ell+1}=2c_{\ell}-b_{\ell}$ explaining the relation $b_\ell=2c_\ell$ easily spotted from the above table.



This approach obviously generalizes to powers of any sum of three squares - simply arrange the coefficient of $k$ to be zero. OTOH this is unlikely to lead to a list of ALL presentations as sums of three squares.
A: Continuing on from my previous answer, I’ve found three more infinite families that can be generated from small solutions.
I now suspect these are just special cases of a more general parametric.
My apologies for any typos, I did this in a rush.

$$(2,9,2,2,1)$$
$$(4,81,6,6,3)$$
$$(6,729,18,18,9)$$
$$(8,6561,54,54,27)$$
$$(10,59049,162,162,81)$$
$$(2c,3^2c,3^{c-1}*2,3^{c-1}*2,3^{c-1}), c>0$$

$$(4,81,8,4,1)$$
$$(6,729,24,12,3)$$
$$(8,6561,72,36,9)$$
$$(10,59049,216,108,27)$$
$$(2+2d,3^{2+2d},3^{d-1}*8,3^{d-1}*4,3^{d-1}), d>0$$

$$(4,81,7,4,4)$$
$$(6,729,21,12,12)$$
$$(8,6561,63,36,36)$$
$$(10,59049,189,108,108)$$
$$(2+2e,3^{2+2e},3^{e-1}*7,3^{e-1}*4,3^{e-1}*4), e>0$$

Update 29 Nov 2016.
I’ve assumed and used the most obvious method of generating new solutions in my answers, but neglected to spot its generality; multiplying through by a constant $3^k$.
Sorry.
When $(q,n,x,y,z)$ is a solution, then new solutions are given by
$$(q+2k,3^{2k}n,3^kx,3^ky,3^kz)$$
