Find 2 integers $t < 419^5$ s.t. $t^2 ≡ 5\mod 419^5$
I'm pretty sure this has something to do with Hansel's lemma but I'm only finding examples with multi term polynomials that have been confusing to follow. If someone could point me in the direction of a similar example or explain how it works that would be awesome. Thanks!
To simplify the reasoning, let $p=419, k=5, a=5;\;$ i.e. you want to compute a root $ r^2\equiv a \bmod p^k$. For a solution with $k=2$ see my answer https://math.stackexchange.com/a/1895883/61216 where I compute a solution $\bmod p^2$.
In the table below I show the lifting steps for the root $r_0\equiv\sqrt{a}\equiv 41 \bmod p$
r = r0 = 41
z = (2r0)^(-1) mod p = 46
j=1
p^j = 419
x = (a-r^2)/p^j = -4
x = x*(2r0)^(-1) mod p^j = 235
r = r + x*p^j = 98506
j=2
p^j = 175561
x = (a-r^2)/p^j = -55271
x = x*(2r0)^(-1) mod p^j = 90949
r = r + x*p^j = 15967195895
j=3
p^j = 73560059
x = (a-r^2)/p^j = -3465893695780
x = x*(2r0)^(-1) mod p^j = 19468360
r = r + x*p^j = 1432109677429135
j=4
p^j = 30821664721
x = (a-r^2)/p^j = -66542094554315137820
x = x*(2r0)^(-1) mod p^j = 8060623011
r = r + x*p^j = 248443251997096924066
p^k = p^5 = 12914277518099
r mod p^k = 8302875642540
Now check that $8302875642540^2 \equiv 5 \bmod{419^5}.$ Now repeat the corresponding steps for the other root $-41 \equiv 378 \bmod 419$ to get the solution $4611401875559.$
Note that for greater values of $k$ it is faster to compute the lifted solutions $\bmod p^{2^j}\;$ (quadratic Hensel lifting). For another references see also the section Powers of odd primes of John Cook's Solving quadratic congruences and the Wikipedia example section.
