Hensel's Lemma: $f'(x) \equiv 0 \pmod{p}$ case.

I understand Hensel's Lemma and how you lift a root $f(b_{j}) \equiv 0 \pmod{p^\alpha}$ to one $f(b_{j+1}) \equiv 0 \pmod{p^{\alpha+1}}$, as long as $f'(b_{j}) \not\equiv 0 \pmod{p}$.

The equation is actually quite simple: $b_{j+1} \equiv b_{j} - f(b)*(f'(a)^{-1}) \pmod{p^{\alpha+1}}$.

My question is what happens when $f'(b) \equiv 0 \pmod{p}$.

The best I can find is that there are multiple solutions, but nothing I can find says how to find them. Is there a nice equation for $b_{j+1}$ (or the multiple values it can take on) given $b_{j}$.

I see nobody has answered this yet. As Greg Martin points out, Niven/Zuckerman/Montgomery have some material on this (Section 2.6 in the Fifth Edition): Hensel's Lemma for the case $f'(r)\not\equiv 0\pmod{p}$; a slightly more general version that says that if $f'(r)\equiv 0\pmod{p}$ but you can lift the solution to a "high enough" power of $p$, then you can keep lifting it (uniquely); and a discussion of what happens in the other cases.

Hensel's Lemma. Suppose that $f(x)$ is a polynomial with integer coefficients. If $f(a)\equiv 0\pmod{p^j}$ and $f'(a)\not\equiv 0\pmod{p}$, then there is a unique $t$ (modulo $p$) such that $f(a+tp^i)\equiv 0\pmod{p^{j+1}}$.

The formula, as noted, is $$a_{j+1} = a_j - f(a_j)\overline{f'(a)},$$ where $\overline{f'(a)}$ denotes the modular inverse of $f'(a)$ modulo $p$. This is really the modular version of Newton's Method; you can view $a_1,a_2,a_3,\ldots$ as a sequence of approximations (in the $p$-adic norm), and the sequence $(a_1,a_2,a_3,\ldots)$ yields a $p$-adic solution to $f(x)= 0 $.

What happens if $f'(a)\equiv 0 \pmod{p}$?

Edited. Consider the Taylor expansion of $f(x)$ at $a$: $$f(a+h) = f(a) + f'(a)h + \frac{1}{2}f''(a)h^2 + \cdots + \frac{1}{n!}f^{(n)}(a)h^n,$$ where $n$ is the degree of $f$. Note that a term $c_kx^k$ in $f(x)$ will result in $$\frac{k(k-1)(k-2)\cdots(k-j+1)}{j!}c_kx^{k-j} = \binom{k}{j}c_kx^{k-j}$$ in $\frac{1}{j!}f^{(k)}(x)$; this has integer coefficients, so each of the coefficients $\frac{1}{j!}f^{(j)}(a)$ is an integer if $f(x)$ has integer coefficients and $a$ is an integer.

Now assume that $f(a)\equiv 0 \pmod{p^j}$ and $f'(a)\equiv 0 \pmod{p}$; then $f(a+tp^j)\equiv f(a)\pmod{p^{j+1}}$ for all integers $t$, since we have: $$f(a+tp^j) = f(a) + tp^jf'(a) + \frac{t^2p^{2j}f''(a)}{2} + \cdots + \frac{t^np^{nj}f^{(n)}(a)}{n!},$$ and $\frac{f^{(k)}(a)}{k!}$ is an integer. So if $f(a)\equiv 0\pmod{p^{j+1}}$, then $f(a+tp^j)\equiv 0\pmod{p^{j+1}}$ for all $t$. That is: if the solution lifts, then the single root modulo $p^j$ lifts to $p$ roots modulo $p^{j+1}$. If $f(a)\not\equiv 0\pmod{p^{j+1}}$, then none of the integers that lie above $a$ modulo $p^{j+1}$ can be roots, and there are no roots lying above $a$.

So either you can lift to all residue classes modulo $p^{j+1}$ that are above $a$, or to none.

If the power of $p$ that divides $f(a)$ is sufficiently high compared to the power of $p$ that divides $f'(a)$, then you can still rescue "lifting":

Generalized Hensel's Lemma. Let $f(x)$ be a polynomial with integral coefficients. Suppose that $f(a)\equiv 0 \pmod{p^j}$, $p^{\tau}||f'(a)$, and that $j\geq 2\tau+1$. If $b\equiv a \pmod{p^{j-\tau}}$, then $f(b)\equiv f(a)\pmod{p^j}$ and $p^{\tau}||f'(b)$. Moreover, there is a unique $t$ (modulo $p$) such that $f(a+tp^{j-\tau})\equiv 0 \pmod{p^{j+1}}$.

Above, $p^{\tau}||f'(a)$ means that $p^{\tau}|f'(a)$, but $p^{\tau+1}$ does not divide $f'(a)$. If $\tau=0$, then we get Hensel's Lemma.

Proof. If $f(a)\equiv 0\pmod{p^j}$, then plugging in $b=a+tp^{j-\tau}$ into the Taylor expansion and considering the equation modulo $p^{2j-2\tau}$, we have $$f(b) = f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{2j-2\tau}},$$ and $p^{j+1}$ divides the modulus (since $j-2\tau\geq 1$). So $$f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{j+1}}.$$ Both $f(a)$ and $p^{j-\tau}f'(a)$ are divisible by $p^j$ (since $f'(a)$ is divisible by $p^{\tau}$), so $f(b)\equiv f(a)\equiv 0\pmod{p^j}$. If we divide by $p^j$, we have $$\frac{f(b)}{p^j} = \frac{f(a+tp^{j-\tau})}{p^j} \equiv \frac{f(a)}{p^j} + \left(\frac{f'(a)}{p^{\tau}}\right) t\pmod{p}.$$ The coefficient of $t$ is not divisible by $p$ (since $p^{\tau+1}$ does not divide $f'(a)$), so there is a unique value of $t$ modulo $p$ for which the right hand side is $0$ modulo $p$. This gives the final clause of the theorem. Finally, since $f'(x)$ is a polynomial with integer coefficients, $$f'(a+tp^{j-\tau}) \equiv f'(a)\pmod{p^{j-\tau}}$$ for all $a$; and $j-\tau\geq \tau+1$, so the congruence also holds modulo $p^{\tau+1}$. Since $p^{\tau}$ divides $f'(a)$ but $p^{\tau+1}$ does not, then $p^{\tau}$ divides $f'(a+tp^{j-\tau})$ but $p^{\tau+1}$ does not. $\Box$

So once you get past a certain point, you can continue lifting as with Hensel's Lemma.

Niven/Zuckerman/Montgomery then show this at work with $x^2+x+223\equiv 0\pmod{3^j}$.

Modulo $3$,t he only solution is $x=1$. $f'(1)=3\equiv 0\pmod{3}$, and $f(1)\equiv 0\pmod{9}$, so each of the three congruence classes lying above $1$, namely $1$, $4$, and $7$, are roots modulo $9$. Since $f(1)\not\equiv 0\pmod{27}$, then $1$ does not lift to solutions modulo $3^3$. Same thing with $f(7)$. On the other hand, $f(4)\equiv 0 \pmod{27}$, so we get three roots modulo $27$, namely $4$, $13$, and $22$. Each of these is still $0$ modulo $81$, so each of these lifts to three solutions modulo $81$. That is, we have nine solutions modulo $81$, namely $4$, $31$, and $58$ (lying over $4$); $13$, $40$, and $67$ (lying over $13$); and $22$, $49$, and $76$ (lying over $22$).

Since $f(4)\equiv 0 \pmod{3^5}$ and $3^2||f'(4)$, we get nine solutions of the form $4 + 27t$ modulo $243$; but there is exactly one value of $t$, $t=2$, for which $4+27t$ is a root modulo $3^6$. So we get nine solutions modulo $3^6$, which are of the form $(4+27(2)) + 81t = 58+81t$.

Similarly, $f(22)\equiv 0\pmod{3^5}$, $3^2||f'(22)$, and so there are nine solutions of the form $22+27t$ modulo $3^5$; there is precisely one value of $t$, namely $t=0$, for which $22+27t$ is a solution modulo $3^6$, which gives nine solutions modulo $3^6$ lying above $22$, the ones of the form $22+81t$.

Finally, $f'(13)\equiv 0 \pmod{27}$, so $f(13+27t)\equiv f(13)\pmod{3^6}$, but $3^4||f(13)$, so none of the integers $13+27t$ modulo $81$ lift to solutions modulo $243$.

After this point, we can apply the generalized Hensel's Lemma: for each $j\geq 5$, there are precisely 18 solutions modulo $3^j$, of which 12 do not lift to $3^{j+1}$ and each of the remaining six lifts to three solutions each.

In summary: if $f(a)\equiv 0 \pmod{p}$, and $f'(a)\equiv 0\pmod{p}$, to determine if $a$ can be lifted to solutions modulo arbitrarily large powers of $p$, determine if you can reach the point where the Generalized Hensel's Lemma applies, i.e., when $j\geq 2\tau+1$. It can be shown that the inequality holds whenever $j$ is larger than the highest power of $p$ that divides the discriminant of $f$.