Using Hensel's Lifting Lemma to Solve $x^2 + x + 34 \equiv 0 \pmod{81}$

Question

As in the title, I'm trying to solve $$x^2 + x + 34 \equiv 0 \pmod{81}.$$

Let $f(x) = x^2 + x + 34$ throughout.

I'm using Hensel's lemma, but it's a bit dense and I'm not sure my interpretation is correct. My method involves checking for solutions through mod 3, mod 9, mod 27 and mod 81, and checking the conditions on $f$ and $f'$ each time. But should I check the conditions for mod 81 too? Or just substitute my penultimate solutions into the original congruence? More specifically, in the penultimate step (mod 27) I get the solutions $$x \equiv 4 \pmod{27}, \quad x \equiv 13 \pmod{27}, \quad x \equiv 22 \pmod{27}.$$

Now, is all that remains to substitute $x = 4,13,22$ into the original equation? None of them are solutions and thus by Hensel's lemma there are no solutions?

Answer 1

I'll solve it without using Hensel's Lemma. Multiply both sides by $4$.

$$(2x+1)^2\equiv -135\equiv 27\pmod{81}$$

$\implies 27\mid (2x+1)^2\implies 9\mid 2x+1\implies 81\mid (2x+1)^2$, but $81\nmid 27$. No solutions.

Answer 2

Hensel's lemma is essentially an induction argument that has already taken care of the inductive step, all that's left to do is confirm the base case. You don't have to continually check the derivative, only for this first case.

$$f(x) \equiv 0 \mod p$$ $$f'(x) \not \equiv 0 \mod p$$

These two requirements are all you need to show that a specific x will uniquely lift to an arbitrary power of your prime, $p^k$.

If you do have a solution then you can lift up by then solving for some $x_0$ value that satisfies $f(x_0)\equiv 0\mod p$, you would then solve:

$$f(x_0+px_1) \equiv 0 \mod p^2$$ Then repeat the process again after getting $x_1$ and solve for $x_2$ and so on,

$$f(x_0+px_1+p^2x_2) \equiv 0 \mod p^3$$

Until you've lifted all the way up to the power you need.

Unfortunately here, we do have a guarantee we will get a unique solution, (or even a solution at all!) though the first condition is satisfied the second condition of having the derivative not be 0 is not because it is 0 mod 3.

$$1^2 + 1 + 34 \equiv 0 \mod 3$$ $$2*1+1 \equiv 0 \mod 3$$

In this case Hensel's lemma breaks and this doesn't actually tell us if we have 0, 1, or many roots. If we were working in base 3, it's more clear to state this way, what's really going on is that the $f'(1)$ is essentially what allows us to decide the next digit. Without it, we are at the mercy of whatever works or doesn't. There's not much easier way of saying this without me just reproducing the proof of Hensel's lemma itself here.

So in this particular example, we were able to have:

x=1 as a solution to $f(x) \equiv 0 \mod 3$

x = 1, 4, 7 as solutions to $f(x) \equiv 0 \mod 9$

x = 4, 13, 22 as solutions to $f(x) \equiv 0 \mod 27$

no solutions to $f(x) \equiv 0 \mod 81$

So that's really just to show how when $f'(x) \equiv 0 \mod p$ really does lead to having 0, 1, or multiple solutions possibly. They don't necessarily have to terminate for higher powers of p either, it just happened to in this example.

Answer 3

You probably can't use Hensel's Lemma:

we need $f'(x) = 2x + 1 \not \equiv 0 \mod 3$ so we need $x \equiv 0, 2 \mod 3$ and that just isn't likely to solve $x^2 + x + 7 + 27 \equiv 0 \mod 3^k$

But $x^2 + x + 34 \equiv x^2 - 80x + (27 + 7) \equiv$

$x^2 -80 x + 40^2 - 40^2 + (27+7) \equiv $

$(x-40)^2 -(27 + 13)^2 + (27 + 7) \equiv $

$(x-40)^2 - 26*27 - 13^2 + (27 + 7)\equiv $

$(x - 40)^2 - 25*27 - 169 +7\equiv $

$(x-40)^2 - 27 - 7+7 \equiv (x-40)^2 - 27 \mod 81$

$\implies (x-40)^2 \equiv 27 \mod 81$.

Which means $27 + 81k$ is a perfect square for some $k$.

So $27(3k + 1)$ is a perfect square. But as $3\not |3k + 1$ that is impossible.

So there are no solutions.

.....

(Or in hindsight: $x^2 + x + 34 \equiv 0 \mod 81 \iff$

$x^2 + x \equiv -27 - 7 \mod 81\iff$

$4x^2 + 4x \equiv -4*27 - 28 \equiv -5*27 - 1\equiv 27 -1 \mod 81\iff$

$4x^2 + 4x+1 = (2x + 1)^2 \equiv 27 \mod 81$

Same contradiction.)