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

$ \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$.