Find all $x\in\mathbb{Z}$ such that \begin{equation}|x^2+1|_5\le 5^{-4},\end{equation} where $|m|_p$ is the $p$-adic valuation of $m$.
The solution given by my instructor is as follows: Take $x_0=a_0=2$ to be the initial approximation such that $|a_0^2+1|_5=|5|_5=1$. Now we take $x_1=a_0+5a_1$ and want $(2+5a_1)^2\equiv -1\pmod{5^2}$, which is equivalent to $a_1=1$. This yields $|x_1^2+1|_5=5^{-2}$. Applying this approach again gives $a_2=2$ and $x_2=7+2\cdot 5^2=57$. Similarly $a_3=1$ and $x_3=57+1\cdot 5^3=182$, so $x=182$ is such a solution.
I don't understand this solution whatsoever; more specifically, I don't know what motivates the choice of $x_0=a_0=2$, and I don't understand the general strategy behind the solution. When the instructor writes that $x_1=a_0+5a_1$, I cannot see where the $5a_1$ term comes from. My understanding is that the next step is just a rewriting of the condition that we want $|x^2+1|$ to be $5$-adically small, but I don't 'get' it. Any help would be great!
Write the inequality as a congruence: it is asking you to solve $x^2 + 1 \equiv 0 \bmod 5^4$. It's very important to realize $p$-adic absolute value upper bounds are just congruences modulo a power of $p$ using another notation: the bound $|a-b|_p \leq 1/p^r$ where $a$ and $b$ are integers and $r$ is a positive integer says the same thing as $a \equiv b \bmod p^r$.
When a congruence holds mod $5^4$ it has to hold mod $5$, so $x^2 + 1 \equiv 0 \bmod 5$, and by a direct check the solutions are $x \equiv 2 \bmod 5$ and $x \equiv 3 \bmod 5$. That's why the option $a_0 = 2$ came up. The other option is $a_0 = 3$ (when $0 \leq a_0 \leq 4$).
When $x^2 + 1 \equiv 0 \bmod 5^4$ and $x \equiv 2 \bmod 5$, $x = 2 + 5y$ where $y$ is an integer. So $(2 + 5y)^2 + 1 \equiv 0 \bmod 5^4$. Reduce both sides mod $5^2$: $(2 + 5y)^2 + 1 \equiv 0 \bmod 5^2$. Expand the left side: $$ 4 + 20y + 25y^2 + 1 \equiv 0 \bmod 5^2, $$ so $5 + 20y \equiv 0 \bmod 25$. Divide through by $5$: $1 + 4y \equiv 0 \bmod 5$, so $y \equiv 1 \bmod 5$. Then $y = 1 + 5z$, so $x = 2 + 5y = 7 + 25z$. Plug that into $x^2 + 1 \equiv 0 \bmod 5^3$ to determine $z \bmod 5$, and repeat. Then do the same thing when $x \equiv 3 \bmod 5$.