0
$\begingroup$

I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class.

The specific question is solve $x^2 =-3\pmod{13^3}$.
As far as I can figure out I need to let $f(x) = (x^2)+3$ and then try to solve $f(x)= 0 \pmod{13^3}$. Beyond that I can't really understand what is going on.

All of the questions are of the form $f(x)= a \pmod{b^n}$. I've only been able to find help on questions where $b^n$ doesn't only have one prime factor and you split the question into two or more equations and solve, and as far as I have seen solving for $x^2 = -3\pmod{13^3}$ gives incorrect answers or leaves some out.

Any help would be much appreciated!

$\endgroup$
  • 1
    $\begingroup$ Are you familiar with Hensel lifitng or Newton iteration? $\endgroup$ – Bill Dubuque Dec 9 '18 at 15:54
  • $\begingroup$ e.g. see this answer and other answers there. Search on "Hensel" for more. $\endgroup$ – Bill Dubuque Dec 9 '18 at 16:01
0
$\begingroup$

You must first solve the congruence $x^2\equiv -3\pmod{13}$. To do this note that $x_o\equiv 6\pmod{13}$ and $x_1\equiv 7\pmod{13}$ are solutions as $x_o^2=6^2=36\equiv -3\pmod{13}$ and $x_1^2=7^2=49\equiv -3\pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12\not\equiv 0 \pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14\not\equiv 0 \pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})\overline{f'(x_{k-1})}$$ After you find these two solutions to the congruence $x^2\equiv -3\pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2\equiv -3\pmod{13^3}$. Hope this helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.