# How to: $f(x)$ congruent to $a \pmod{b^n}$

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!

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

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!