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

-
do you mean integer? – Alex Oct 11 '12 at 20:23
Can you show that it is true for $k=0$ and $k=1$? How about $k=2$? These cases ought to give you some feeling for how the problem works, and may end up being useful as base cases if you find you want to use induction for the general case. – Henning Makholm Oct 11 '12 at 20:28
yes,$k=0 \ \text{and} \ k=1$ are easy cases. Can't proceed further. – Random Oct 11 '12 at 20:33
Can'tproceed further? In the $k=2$ case it is clear that neither $|x|$ nor $|y|$ can be more than $5$. If everything else fails, then there are only 121 cases to check, which quickly becomes smaller by application of symmetries. – Henning Makholm Oct 11 '12 at 20:35
Have you done properties of Gaussian integers? – André Nicolas Oct 11 '12 at 22:17

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

-
Thanks for your help. – Random Oct 13 '12 at 8:23

Not a full solution, but enough to get you started:

I assume that you are counting solutions such which differ only by changing sign or by swapping $x$ and $y$ as being distinct?

If you have two numbers $a$ and $b$ which can be written as a sum of two squares in one (essentially distinct) way, then $ab$ can be written as a sum of two squares in two essentially distinct ways - this is covered here: Brahmagupta–Fibonacci identity.

Now we know that $5=2^2+1^2$, and from this we can use the above identity to find solutions of $25 = x^2+y^2$, (i.e. (5,0) and (3,4)) and so on ...

-
Thanks for your help. – Random Oct 13 '12 at 8:22