Find $x,y$ are natural numbers such that $x^2+16=5^y$
My try:
Let $y=2$ so $x=\pm 3$, and $y\ge3$ then $125\mid5^y\rightarrow109\mid5^y-16$.
I think don't exist $x$ such that $x^2\equiv109 \pmod{125}$, but $22^2\equiv 109 \pmod {125}$. So it's wrong.
Please help, thank you!
Clearly $x$ must be odd because $5^y$ is always odd. Write $y = 2q + r$, where $y$ and $r<2$ are two non-negative integers, we work mod $8$ to find $$1 \equiv x^2 \equiv 5^y = 5^{2q + r} = 25^q \cdot 5^r = 1^q \cdot 5^r =5 ^r\pmod 8$$ yielding $r = 0$. Thus, we have that $$x^2 + 4^2 = \left(5^q\right)^2.$$ Now we know there is an $n\in\mathbb{N}$ such that $5^q = x + 2n$, which we substitute in to find $x^2 + 4^2 = (x + n)^2$ which yields $(x + n)n = 4$. This has the only solution of $(x, n) = (3,1)$. Therefore $$5^q = x + 2 = 3 + 2 = 5,$$ which gives us $q = 1$ and $y = 2q = 2 \cdot 1 = 2$. Therefore, the only solution is $(x, y) = (3,2)$.