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

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.

At heart, $a^2+b^2$ can be seen as the square of 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.

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$