# Given a fixed positive integer $k$, find the number of pairs of integers $(x,y) \in \mathbb{Z}^2$ such that $x^2+y^2=5^k$

Given a fixed positive integer $k$, find the number of pairs of integers $(x,y) \in \mathbb{Z}^2$ such that

$$x^2+y^2=5^k$$

Attempt: Clearly $x$ and $y$ cannot have the same parity. Assume that $x=2a+1$ and $y=2b$ for some integer $a,b \in \mathbb{Z}$. We also have $x^2 \leq 5^k$ and $y^2 \leq 5^k$.

Then we have $a \leq \frac{5^{\frac{k}{2}}-1}{2}$ and $b \leq \frac{5^{\frac{k}{2}}}{2}$. From here I don't know how to compute the number of pairs of $a$ and $b$ which satisfies the equation.

• why not say $x=5a+1,y=5b+2$? – chenbai May 23 '15 at 7:42
• What motivates the equations? – Idonknow May 23 '15 at 7:49

By using the factorization over $\mathbb{Z}[i]$, that is a Euclidean domain hence a UFD, it is not difficult to prove that:

$$r_2(n)=\#\{(x,y)\in\mathbb{Z}^2:x^2+y^2=n\}$$ is given by: $$r_2(n) = 4(\chi_4 * 1)(n) = 4\,\sum_{d\mid n}\chi_4(d)=4\left(d_1(n)-d_3(n)\right)$$ where $d_1(n)$ is the number of divisors of $n$ of the form $4k+1$ and $d_3(n)$ is the number of divisors of the form $4k+3$. If $n=5^k$ there is no divisor of the form $4k+3$, hence: $$r_2(5^k) = 4\cdot d(5^k) = \color{red}{4k+4}.$$ That can also be proved by induction. We have: $$5 = (\pm 1)^2+(\pm 2)^2$$ and through the Lagrange identity: $$(1^2+2^2)\cdot (a^2+b^2) = (a+2b)^2+(2a-b)^2$$ we may see that we gain exactly four representations every time $k$ raises by one.

Work in the ring of Gaussian integers, $\mathbf{Z}[i]$, a UFD, where we have the factorization $x^2+y^2= (x+iy)(x-iy)$. As $5=(2+i)(2-i)$, we have $5^k =(2+i)^k(2-i)^k$. Now writing $(2+i)^k =a+ib$, you get a solution $5^k=a^2+b^2$.

• OP is looking for the count of all such pairs - but with a little more information, this answer should be adaptable to give that as well. – Steven Stadnicki May 23 '15 at 7:57
• Also, a and b should be integers. I think we need to now find for what integer values of k, a and b turn out to be integers. They are not always integers. +1 from me though. Very smart approach. Seems it gives $a + ib = \sqrt{5}(\cos{\alpha} + i.\sin{\alpha})$, where $\tan{\alpha}=1/2$. I think the question is now: for what $k$ are both $\sqrt{5}^k\cos{k\alpha}$ and $\sqrt{5}^k\sin{k\alpha}$ integers?! – peter.petrov May 23 '15 at 8:04
• a and b are always integers since we can expand $(2+i)^k, k \in \Bbb Z$ using the binomial expansion. – Asvin May 23 '15 at 8:20

It is known that the Gaussian integers $\mathbb{Z}[u]$ is an UFD with

• $4$ units: $1, i, -1, -i$
• $5$ can be factorized as $(2+i)(2-i)$ where $2 \pm i$ are primes in $\mathbb{Z}[i]$.
Furthermore, $2 + i$ and $2-i$ are inequivalent to each other (i.e their ratio is not an unit).

The $UFD$ property of $\mathbb{Z}[i]$ tells us when one factorize $5^k$ as $a^2 + b^2 = (a+bi)(a-bi)$. The possible choices of $a+bi$ has the form

$$a + bi = i^e (2+i)^{k-\ell}(2-i)^\ell \quad\text{ with }\quad \begin{cases} 1 \le e < 4,\\ 0 \le \ell \le k \end{cases}$$

Furthermore, all these choices give a different pair of $(a,b)$.

What this means is the number of $(a,b) \in \mathbb{Z}^2$ such that $5^k = a^2 + b^2$ is simply $4(k+1)$.