Number of solutions of equations mod $p^n$

Using Hensel's lemma, it is easy to prove that if $p$ is a prime with $p\equiv 1\mod 3$ then the equation $x^2-x+1=0$ has at least two solutions $\mod p^n$ for all $n\geq 1$. Are there more than two solutions?. Of course, the anwer is not when $n=1$ but what happens if $n\gt 1$?. I have many more equations to analyze so it would be interesting to find an answer for more general equations.

It is convenient to note that $x$ is a solution of $x^2-x+1\equiv 0\pmod{p^n}$ if and only if $x\equiv -t\pmod{p^n}$, where $t$ is a solution of $t^2+t+1\equiv 0\pmod{p^n}$.
Since $p$ is an odd prime, there is a primitive root $g$ modulo $p^n$. To show that there are exactly $2$ solutions of $t^2+t+1\equiv 0\pmod{p^n}$, it is enough to show that the congruence $t^3-1\equiv 0\pmod{p^n}$ has exactly $3$ solutions. We look for solutions of the shape $g^k$.
We have that $g^k$ is a solution of the congruence $t^3-1\equiv 0\pmod{p^n}$ if and only if $g^{3k}\equiv 1\pmod{p^n}$.
Note that $\varphi(p^n)=(p-1)p^{n-1}$. Let $p=1+3m$. If we put $k=mp^{n-1}$, then $g^{3k}\equiv 1\pmod{p^n}$. And in general, $g^{3k}\equiv 1\pmod{p^n}$ if and only if $\varphi(p^n)$ divides $3k$. For $0\le k\lt \varphi(p^n)$, this happens if and only if $k=0$, $m$, or $2m$.
• question: why did you prefer $t^3-1$ over $t^2+t+1=(t+\frac{1}{2})^2+\frac{3}{4}$ and the three solutions must be counted with multiplicity for $p=3$ the solution $t=1$ is a double root – Elaqqad May 2 '15 at 1:19
• The problem is about primes of the form $3k+1$. As to $t^3-1$, it looks nicer than $(t+1/2)^2+3/4$, and a basic chapter in elementary number theory has to do with order. Also, the same idea would work with longer sums. But it is true that $(2t+1)^2+3$ would work nicely, and then it comes down to $x^2\equiv a\pmod{p^n}$. – André Nicolas May 2 '15 at 1:42