1
$\begingroup$

enter image description here

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Cf. Hensel's lifting lemma $\endgroup$ Nov 9, 2020 at 5:13
  • $\begingroup$ @tkf Hi Thanks for your answer. What do you mean by 'solve 13|w+ 2ax' ? $\endgroup$
    – siegfried
    Nov 9, 2020 at 5:16
  • $\begingroup$ @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. $\endgroup$
    – tkf
    Nov 9, 2020 at 5:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .