So the theorem of Hensel's Lemma I was given is as follows:
Let $p$ be prime, $f(x) \in \mathbb{Z}[x]$, and $n \geq 2$. Suppose $a$ is a solution to $f(x) \equiv 0 \mod{p^{e-1}}.$ If $gcd(p, f'(a)) = 1$, then $b := a + kp^{e-1}$ is a solution to $f(x) \equiv 0 \mod{p^{e}}$, for which k satisfies $\frac{f'(a)}{p^{e-1}} \equiv -kf(a) \mod{p}$.
As an example, let's say that there are only exactly two solutions $a_1, a_2 \in \mathbb Z_{p^{e-1}}$ for which $f(a_1), f(a_2) \equiv 0 \mod{p^{e-1}}$. Why does $gcd(f'(a_1), p) = 1$? I understand that $gcd(f'(a_1), p) = 1$ implies that there is a unique solution $k_1$ to $\frac{f'(a)}{p^{e-1}} \equiv -k_1f(a) \mod p$, but what if $gcd(f'(a_1), p)$ is a multiple of $p$ where $p \neq 1$? Would that generate more than one solution for $k_1$?
Also, does this theorem give all possible solutions to the congruence equation of $f(x) \equiv 0 \mod{p^{e-1}}$? The theorem seems to say that it helps us find some solutions, but I don't know if it also means that those "some" solutions are all the solutions.
Thanks in advance.
If $p$ is odd, and $f$ is quadratic with two distinct roots, $a_{1,1},a_{1,2}$ modulo $p,$ then $f’(a_{1,i})\not\equiv 0\pmod p$ for $i=1,2.$
This is because, if $f(a)\equiv f’(a)\equiv 0\pmod p,$ $a$ is a repeated root, and $f(x)\equiv c(x-a)^2\pmod p$ for some constant $c\not\equiv 0\pmod p.$
Then we use Hensel’s Lemma to prove by induction on $e$ that there is a distinct pair $a_{e,1},a_{e,2}$ with $f(a_{e,i})\equiv 0\pmod{p^e},$ and $a_{e,i}\equiv a_{1,i}\pmod p$ for $a=1,2.$
That last is the key part. When $p$ is odd and $f$ has distinct roots when $e=1,$ then for any $e,$ each root from the $\pmod p$ equation is a source of a single solution modulo $p^{e}.$
This shows the $a_{e,i}$ are distinct modulo $p^e,$ and since $$f’(a_{e,i})\equiv f’(a_{1,i})\not\equiv 0\pmod p,$$ you have $(f’(a_{e,i}),p)=1.$
So the times Hansel’s Lemma won’t work is when $p=2,$ and when $p$ is odd, but there is a repeated root modulo $p.$
The base example of when things go badly is $f(x)=x^2.$ Then modulo $p^e,$ any multiple of $p^{\lceil e/2\rceil},$ and we get a $p^{\lfloor e/2\rfloor}$ distinct solutions.
Another negative example is $f(x)=x^2+px.$ It has the same roots modulo $p,p^2,$ but there are only $2p$ solutions modulo $p^e$ for $e>2.$
Another bad case is when $f(x)=ax^2+bx+c$ where $p\mid a.$ Then there is at most one root, modulo $p^e.$
For example, when $p=3$ and $f(x)=3x^2+x-1,$ only $1$ is a solution modulo $3.$ $f’(1)\equiv 1\pmod 3.$ So we can use Hensel’s Lemma, and we only get one solution modulo $p^e$ for each $e.$