<s>[INST] Prove that there exists only 2 solutions for $x^2 \equiv 9 \pmod {p^k}$, ($p$ an odd prime > 3 and $x$ a natural number < $n$) It appears that the only two solutions are always $3$ and $p^k-3$, I want to prove this, here has been my approach, I think I am close but just missing something, would really appreciate any help!!!
Suppose, 
$b^2 \equiv 9 \pmod {p^k}$ for ($k \ge 1$)  
$\implies b^2 = 9 + cp^k $ for some integer $c$
I want to find $r$ s.t. $(b+rp^k)^2 \equiv 9 \pmod {p^{k+1}}$
(I.e. since $b \equiv \pm 3$, I want $r \equiv \pm 1$ )
By squaring i get,
$(b+rp^k)^2 \equiv  b^2 + 2brp^k + r^2p^{2k} \equiv   9 \pmod {p^{k+1}}$
Substituting $b^2 = 9 + cp^k$ yields,
$9 + cp^k+2brp^k+r^2p^{2k} \equiv 9 \pmod {p^{k+1}}$
$ \implies (c+2br)p^k+r^2p^{2k} \equiv 0 \pmod {p^{k+1}}$
So I need $r$ s.t.
$c+2br \equiv 0 \pmod p$
Since $b \equiv \pm 3$
$ \implies 2(-3)r \equiv -c \pmod p$ or $2(3)r \equiv c \pmod p$ 
Now I'm kind of stuck, I'm not sure where I need to go from here. I think that if $b\equiv-3$ then I want $r=1$ and if $b\equiv3$ then I want $r=-1$...
I would really appreciate some help! I think I am close!
 [/INST] Let $p\gt 3$. Note that $x^2\equiv 9\pmod{p^k}$ if and only if $p^k$ divides $(x-3)(x+3)$. But $p$ cannot divide both $x-3$ and $x+3$, else it would divide their difference $6$. So $(x-3)(x+3)$ is divisible by $p^k$ if and only if $p^k$ divides $x-3$ or $p^k$ divides $x+3$. Thus there are two solutions, $x\equiv 3\pmod{p^k}$ and $x\equiv -3\pmod{p^k}$. Thse are clearly incongruent modulo $p^k$. 
Remark: The situation is more complicated when $p=2$ or $p=3$. Note for example that the congruence $x^2\equiv 9\pmod{2^3}$ has $4$ solutions. So does the congruence $x^2\equiv 9\pmod{3^2}$. A complete analysis for these special primes is not difficult. 
</s>