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.