$p$-adic approximation I am asked to find $x\in\mathbb{Z}$ s.t. $|x^2+1|_5\leq5^{-4}$.
I have a method of doing it but I'm not sure if it's right and whether my conclusion is correct either. It also seems exceedingly long and not very efficient so perhaps there might be a better method of going about it.
Here's what I did:
First let $x_0=a_0=2$ and this gives $|x_1^2+1|_5=5^{-1}$.
Next consider $x_1^2=(a_0+5a_1)^2=-1\mod5^2$, for which I solve to get $a_1=1$. This in turn gives me that $|x_1^2+1|_5=5^{-2}$, so I think I may be on the right track.
I then considered $x_2^2=(a_0+5a_1+5^2a_2^2)^2=-1\mod5^3$ but then after doing all the algebra, I got $4a_2^2=3 \mod 5$ which has no solutions since 3 is not a quadratic residue modulo $5$. Apart from the initial choice of $a_0$, there is no room for choices for the rest of the $a_i$'s.
The other option was for me to let $x_0=a_0=3$. This gives me $a_1=3$ but when I worked out the algebra for $a_2$, I got $a_2^2=2 \mod 5$, which again has no solution for the same reason.
Is this sufficient to say that no such $x$ exists for my equation?
 A: You are working in the ring $\mathbb Z/(5^4\mathbb Z)$, or if you’re very well-educated, in the $5$-adic integers $\mathbb Z_5$. Either way, your quickest route to a root of a polynomial is Newton-Raphson, which I hope you know from high-school Calculus. The function whose root you want is $f(x)=x^2+1$, and its derivative is $f'(x)=2x$. If your first guess is $x_0=2$ (since $2^2+1\equiv0\pmod5$), you calculate the error, which is $5$, and divide by $f'(2)=4$ and subtract this from $2$ to get $3/4=x_1$, your second guess. Now the error is $25/16$, and you divide by $2x_1$ and subtract from $x_1$ to get $x_2=-7/24$. Now $(-7/24)^2+1=625/576$, voilà.
I might point out that when you’re seeking a $(q-1)$-th root of unity when the residue field is $\mathbb F_q$, the field with $q$ elements, there is a conceptually easier but computationally longer method, namely repetitive raising to the $q$-th power. Here, $i$ is a fourth root of unity, and $q=5$, so your sequence is
$x_0=2$, $x_1=x_0^5=32$, $x_2=x_1^5$, etc., and you notice that $x_1^2+1\equiv0\pmod{5^2}$, $x_2^2+1\equiv0\pmod{5^3}$, etc. It’s easy enough to prove that this works.
