$\exists a, b \in \mathbb{Z}$ such that $a^2 + b^2 = 5^k$

I saw this problem recently and found an elegant solution to it, and was curious to see if anybody would think of something else. Nice solutions to nice problems are fun to see!

Problem: Prove that, for all non-negative integers $k$, there exist integers $a$, $b$ such that $a^2+b^2=5^k$.

Bonus: Prove that $(a,b)=1$.

Solutions Collecting From Web of "$\exists a, b \in \mathbb{Z}$ such that $a^2 + b^2 = 5^k$"

At heart, $a^2+b^2$ can be seen as the square if the distance of $a+bi$ to $0$ in the complex numbers. And if $w,z$ are complex numbers, then $|wz|=|w|\cdot |z|$, so $|wz|^2 = |w|^2\cdot |z|^2$.

That means that if $a+bi = (2+i)^n$ then $a^2+b^2 = |a+bi|^2 = \left(|2+i|^2\right)^n = 5^n$.

This approach gets you $a,b$ relatively prime and non-zero.

The other way is just to take the case of $n=2m$ even first:

$$5^{2m} = \left(5^m\right)^2 +0^2$$

For $n=2m+1$ odd, you get:

$$5^{2m+1} = \left(2\cdot 5^m\right)^2 + \left(1\cdot 5^m\right)^2$$

There is another way, closely associated with the complex answer, using determinants of matrices of the form:

$$\begin{pmatrix}x&y\\-y&x\end{pmatrix}$$

Such matrices are closed under multiplication, and the determinant is $x^2+y^2$.

Since the product of determinants is the determinant of the product, you only need to find a solution of $x^2+y^2=5$ and raise that matrix to the $n$th power.

This gives you exactly the same answer(s) as my first approach, since the ring of matrices of this form is “isomorphic” to the complex numbers. But the determinant is in some ways an “algebraic” answer, compared to the distance property.

HINT:

Using induction:

$5^1=2^2+1^2$

Let $5^k=a^2+b^2$

$5^{k+1}=(a^2+b^2)(2^2+1^2)=(2a\pm b)^2+(2b\mp a)^2$ (Brahmaguptaâ€“Fibonacci identity)

This invites a little generalization: as we which numbers are expressible as the sum of two squares.

Take the ring $\mathbb{Z}[i]$ and the norm function
$$N(x+iy) = x^2 + y^2$$
Then $N(z_1z_2) = N(z_1)N(z_2)$. So just take
$$z = (2+i)^k = a+bi$$
Then $a^2+b^2 = N(z) = N(2+i)^k = 5^k$