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.

Thanks in advance.


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$.

  • $\begingroup$ @Diego: Thanks for the edit! $\endgroup$ – André Nicolas May 1 '15 at 23:29
  • $\begingroup$ 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 $\endgroup$ – Elaqqad May 2 '15 at 1:19
  • $\begingroup$ 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}$. $\endgroup$ – André Nicolas May 2 '15 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.