4
$\begingroup$

Solve $3x^2+6x+5\equiv 0\pmod{89^2}$.

To do this, I first solved $3x^2+6x+5\equiv 0\pmod{89}$.

This has a solution since $3x^2+6x+5 = 3(x+1)^2 + 2$ and $3(x+1)^2 \equiv -2 \pmod{89}$ has a solution since $(3,89)=1$, we can check whether $(x+1)^2 = 3^{-1}(-2)\pmod{89}$ which is equivalent to calculating $\left(\dfrac{3^{-1}(-2)}{89}\right)$. The value is 1, so this is a quadratic residue. Since we have a number that when squared gives us this, we have a solution to the polynomial congruence mod 89. Since we have 1, we have 2 since solutions come in pairs $\{\pm x_0\}\pmod{89}$.

Here is my question: without finding the residue, how can I use Hensel's lemma to see whether I can lift the solutions to solutions modulo $89^2$?

I hope someone can help. Thank you.

  • 0
    The only requirement to be able to lift it is to make sure that $f'(r)\not\equiv 0\pmod{89}$. The derivative is $6x+6 = 6(x+1)$; in order to verify that it is not $0$ modulo $89$, all you have to do is make sure that the answer you got $\pm x_0$, is not $1$, which seems easy.2011-12-12
  • 0
    EDIT: Okay, so if I get $x_0\neq \pm 1$, then $89\nmid 6(x_0+1)$. This will generate two new solutions modulo $89^2$ then. But if $89\mid 6(x_0+1)$, I have to check whether $89^2\mid 3x_0^2 +6x_0+5$. If it does, I get 89 new solutions for each $x_0$. If not, I have no solutions for either of them. Is that right?2011-12-12
  • 0
    The solutions *do* lift: the answer you get cannot be $1$ or $-1$, because $3+6+5\not\equiv 0\pmod{89}$, and $3-6+5\not\equiv 0\pmod{89}$. By Hensel's Lemma, if $f(r)\equiv 0\pmod{89}$ and $f'(r)\not\equiv 0\pmod{89}$, then $r$ lifts uniquely to a solution $s$ of $f(s)\equiv 0\pmod{89^2}$. So each of $x_0$ and $-x_0$ lift to unique solutions modulo $89^2$ (in fact, you can lift them to solutions modulo $89^k$ for any $k$).2011-12-12
  • 0
    Perfect OK I was just making sure. I will delete the post. I didn't know if it was enough to test $\pm 1 \pmod{89}$.2011-12-12
  • 0
    In this case it is, because those are the only possible values of $r$ that can mess up your Hensel lift. In general, you can check the zeros of $f'(x)$ (assuming you can find them, which in this instance we can) and see if any of them satisfy the original equation. Essentially, you are checking to see whether the polynomial has repeated roots modulo $p$. Since this polynomial is not a perfect square modulo $89$, its roots are simple roots and so they lift.2011-12-12
  • 0
    P.S. No reason to delete the question! Why not post your own answer? Explain why what I've outlined works, and then maybe even compute the solution if you feel like it.2011-12-12
  • 0
    Okay. Thanks a lot. Is there a general method to find the root of that equation? Also, what if $(3,89)\neq 1$? I try to invert and then I cant compute the Legendre symbol? Do I conclude no solutions modulo 89? Edit: I guess in that case do I use the Chinese remainder theorem and check if it has solutions modulo the factorization then conclude they solve modulo the product then worry about lifting? Sorry for the comment questions...2011-12-12
  • 0
    Note that $89$ is a prime. The usual quadratic formula works for quadratic equations modulo any odd prime, so "all" you need to do is check if the discriminant is a square, and if so find the square root (there are heuristics and algorithms for doing so). For an arbitrary modulus, you can use the Chinese Remainder Theorem and Hensel's Lemma to reduce to the case of prime moduli, and handle the troublesome cases (when the prime divides the leading coefficient but the modulus is divisible by a higher power of the prime) directly.2011-12-12
  • 0
    Okay, I think i kind of lost you toward the end"(when the prime divides the leading coefficient...)"but I don't think my exam will be that technical. :) I had just one more concern: When dealing with higher power congruences are we in deep trouble because the difficulty of finding nth residues? Thanks so much for your detailed help!!!2011-12-12
  • 0
    Hensel's Lemma tells you how to go from a solution modulo $p^i$ to a solution modulo $p^{i+1}$; it is utterly silent on the question of how to find the first solution; but the value of $i$ is irrelevant. As far as solving polynomials of degree higher than $2$, the problems have to do with our inherent difficulty in solving them, rather than any particular issue with $n$th residues. Quadratic residues are used to solve quadratic polynomials because of the quadratic formula; you can use the Cardano formulas for cubic polynomials ($p\neq 2,3$); after degree 4, though, no ready formulas.2011-12-12

0 Answers 0