x^2 + 1 == 0 (mod 5^3).

[brute26]

How would i start to solve this problem?

x^2 + 1 == 0 (mod 5^3).

Find all solutions.

How do i know how many solutions there are? If i reduce it to
x^2 + 1 == 0 (mod 5), i get that x= 2,3,7,8,12, etc.

[Gokul43201]

All solutions of the latter will not be solutions of the former.

If 0<=x<125 is a root of x^2 +1 \equiv 0 (mod~ 5^3) then x satisfies x^2 +1 \equiv 0 (mod~ 5^2) and is of the form y+25n, 0<=n<5, 0<=y<25.

Clearly y=7, 18 works.

Also since these do not satisfyf'(y) = 2y \equiv 0 (mod~ p) , there is only one n, which will give you the principal roots 57 and 68.

I've left some gaps for you to figure out and fill.

[primarygun]

How about this method?
x^2+1=125t (t:+ integer)
x=1/2* root 4(125t-1)