# Solving quadratic congruences modulo powers of nonprimes 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.

• Hint for (a): $x^2\equiv-1\pmod3$ has no solutions; for (b): same $\pmod7$; for (d) there are no solutions $\pmod{13}$ Nov 9, 2020 at 4:45
• Also $8\not\!|13$ so (d) has no solutions.
– tkf
Nov 9, 2020 at 4:52
• (с) has two solutions Nov 9, 2020 at 6:11

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$$.

• Nov 9, 2020 at 5:13
• @tkf Hi Thanks for your answer. What do you mean by 'solve 13|w+ 2ax' ? Nov 9, 2020 at 5:16
• @siegfried. At this stage of the process, you have an integer $a$ and an integer $w$. You need to find an integer $x$ such that $13|w+2ax$. You can do this via Euclid's algorithm.
– tkf
Nov 9, 2020 at 5:19