<s>[INST] number of integral solutions for $x^2+y^2=5^k$ Prove that the equation $x^2+y^2=5^k$ has $4k+4$ integral solution.
Any ideas would be appreciated.
Thanks
 [/INST] Lets use Strong form of mathematical induction.
Base Case: $k=0$ and $k=1$ are obvious.
Assume $x^2+y^2=5^k$ has exactly $8$ solutions $(x,y)$ such that $x$ and $y$ are not divisible by $5$ along with $4k-4$ solutions of the form $(5a,5b)$ where $(a,b)$ are solution of $a^2+b^2=5^{k-2}$. We need to show similar for $k+1$.
Note that $(x,y)$ are all obtained from each other by permutations of $x$ and $y$ and changes of signs,lets call them new solutions.
If $x^2 + y^2$ be divisible by $5$. Then $(x + 2y)(x − 2y) = x^2 + y^2 − 5y^2$ is also divisible by $5$. Hence, one of the numbers $x + 2y$ and $x − 2y$ is divisible by $5$. Note that if both are divisible by $5$, then both $x$ and $y$ are divisible by $5$.
If $(x, y)$ is a new solution of equation $x^2 + y^2 = 5^k$ , then $(x + 2y, 2x − y)$ and $(x − 2y, 2x + y)$ are solutions of equation $m^2+n^2=5^{k+1}$ and precisely one of them is new. Hence each new solution pair $(x,y)$ of $x^2+y^2=5^k$ yields $1$ new solution and $1$ not new solution for $x^2+y^2=5^{k+1}$. Hence we are done as there are exactly $8$ new solutions for $x^2+y^2=5^k$ yielding $8$ new and $8$ not new solutions for $x^2+y^2=5^{k+1}$ in the form of $$(\pm (2x \pm y),\pm(x \pm 2y)) \text{ and }(\pm (x \pm 2y), \pm(2x \pm y)).$$
Note that the $8$ not new solutions will be contained in case of $x^2+y^2=5^{k-1}$.
Thanks
</s>