Having problems using Hensel Lifting for Prime Power Moduli We have $P(x) = x^2 + 3x + 9 ≡ 0 \mod(3^i)$, for $i=1,2,3,4$
for $\mod(3): x^2 + 3x + 9 ≡ x^2$, so $x ≡ 0 \mod(3)$ is a solution.
From Hensel lifting, we have $s = x + a\times 7,\ a = [-P(0)\times (1/3)] \times (P'(0))^{-1}$.
Computing for $a$, we get $a = -3 \times (3)^{-1}$. But, $(3)^{-1}$ is when $3a ≡ 1 \mod(3)$, but this has no solutions since $\gcd(3,3)$ is not $1$. Where am I going wrong? Can somebody help me out please? :(
 A: You're trying to use a formula that is only valid when $P'(0)\not\equiv0\pmod3$. In this case, the derivative vanishes at the root in question, so Hensel lifting is more complicated (see this link for a brief description).
A: We go through the lifting process. The case $i=1$ has been dealt with. We now deal with $i=2$. Let $p=3$. Instead of $i$ we will use $k$.  
We have $P'(x)=2x+3$. This is congruent to $0$ modulo $p$. In that case, the Hensel lifting goes as follows:
1) If we have a root $a$ modulo $p^k$, and $p^{k+1}$ divides $P(a)$, then the root $a$ modulo $p^k$ lifts to $p$ roots modulo $p^{k+1}$;
2) If $p^{k+1}$ does not divide $P(a)$, then the root $a$ does not lift to a root modulo $p^{k+1}$.
Currently we are lifting from $k=1$, with $a=0$. Note that $p^2$ divides $P(a)$, so by 1) the root $a=0$ lifts to $3$ roots modulo $p^2$, namely $a\equiv 0$, $3$, or $6$ modulo $9$. 
Now we lift from $k=2$ to $k=3$. First look at $a\equiv 0\pmod{9}$. We have $P(0)\equiv 9\not\equiv 0\pmod{3^3}$, so the root $a\equiv 0\pmod{9}$ does not lift. A similar argument shows that $a\equiv 6\pmod{9}$ does not lift.
Now look at the root $a\equiv 3\pmod{9}$. The number $P(3)$ is divisible by $3^3$, so the root $a\equiv 3\pmod{9}$ lifts to $3$ solutions modulo $3^3$, namely $a\equiv 3$, $12$, and $21$ modulo $3^3$.
We now have $3$ roots modulo $3^3$. For each of them, we investigate liftability to a solution modulo $3^4$. So calculate $P(3)$, $P(12)$, and $P(21)$. 
I expect you can now continue, and finish the analysis for $k=4$. As a start, the root $a\equiv 3\pmod{3^3}$ does not lift.   
Remark: Since we are only asked to go to the small number $3^4$, there are less tedious ways to proceed than Hensel lifting. We went through the process on the assumption that this is the tool you were asked to use.
Since our polynomial is a quadratic, another way to proceed for general $k$ is to multiply by $4$. We get the equivalent congruence $4x^2+12x+36\equiv 0\pmod{3^k}$. Complete the square, and rewrite as $(2x+3)^2\equiv -27\pmod{3^k}$. 
