Solving quadratic congruences modulo powers of nonprimes

Question

I am a bit clueless with this problem. Do I start by finding a primitive root of the modulo or is the Legendre symbol of any relevance here? Please provide me with some hints.

---

My attempt:

Based on the idea of lifting the solution suggested by tkf and JW Tanner, a slightly more intuitive algorithm can be found here: (https://www.uvm.edu/~cvincen1/files/teaching/spring2017-math255/quadraticequation.pdf).

Part a: with CRT, consider the base case $x^2\equiv -1 $mod 3, $x^2\equiv -1 $mod 31. But $(\frac{-1}{3}) =-1$, so there is no solution to the congruence. mod 31 also has no solution as $(\frac{-1}{31}) =-1$.

Part b: the base case $x^2\equiv -1$ mod 7 has no solution. Therefore the overall congruence has no solution.

Part c: For j=1, solve $x_0 \equiv -1 $ mod 13; $x_0=5$.

For $j+1=2$, solve $x_1^2 \equiv -1 $ mod $13^2$; $x_1= x_0 + p^jy_0$. Solve for $y_0$ from: $2x_0y_0 \equiv \frac{-1-x_0^2}{p^j}$ mod 13. $y_0= 5$. Then $x_1= 70$; $70^2\equiv -1$ mod $13^2$.

For $j+1=3$, solve $x_2^2 \equiv -1 $ mod $13^3$; $x_2= x_1 + p^jy_1$. Solve for $y_1$ from: $2x_1y_1 \equiv \frac{-1-x_1^2}{p^j}$ mod 13. $y_1= 1$. Then $x_1= 239$; $239^2\equiv -1$ mod $13^3$.

Repeat this process until $j+1=6$. $x_5= 1999509$. $1999509^2\equiv -1 $mod $13^6$ ($169^3$).

In part c $-1999509$ is the other solution to the congruence.

Part d: Based on part c, this is equivalent as solving $x^2\equiv x_5^2\equiv -1$ mod $169^3$. Consider $x^2\equiv 1999509$ mod $13^6$. $(\frac{1999509}{13})=-1$ suggests that there is no solution to the congruence.

Answer 1

From comments only (c) is left. Here is the general method:

Suppose you know $$13^k|a^2+1,$$

for some integer $a$ and $k\geq 1$.

Then you can find $x$ to solve $$13^{(k+1)}|(a+x13^k)^2+1.$$

Firstly you know there is some integer $w$ with $13^kw=a^2+1$.

Multiply out:

\begin{eqnarray*}(a+x13^k)^2+1&=&a^2+1+x^213^{2k}+2ax13^k\\&=&13^k(w+2ax+x^213^k).\end{eqnarray*}

Thus you just need to solve $13|w+2ax$.

Thus you can solve $$13^k|a^2+1,$$ for $k=1,2,3,4,5,6$.