# What is the solution number of the equation $x^2-x+1\equiv 0 \pmod{p^e}$

What is the solution number of the equation

$$x^2-x+1\equiv 0\pmod{p^e}$$

I know when $e=1$, it is $1+\left(\frac{-3}{p}\right)$, and I guess it is the same for $e>1$, but can anyone provide a proof?

updated:

I know when $e=1$, the number is $$1+\left(\frac{-3}{p}\right)$$

When $e>1$, it is said that the answer is the same, saying that $$1+\left(\frac{-3}{p}\right)=1+\left(\frac{-3}{p^e}\right)$$

That's what puzzling me.

-
How exactly did you obtain that result for $e = 1$? –  TMM Jan 12 '13 at 15:14
@TMM, like the answer bhattacharjee is given. But I need to show $\left(\frac{-3}{p^e}\right)=\left(\frac{-3}{p}\right)$ –  hxhxhx88 Jan 12 '13 at 15:29
I don't think so. We have $\left(\frac{-3}{5}\right)=-1,\left(\frac{-3}{25}\right)=-1$ –  hxhxhx88 Jan 12 '13 at 15:45
Let me rephrase that: $$\left(\frac{-3}{p^e}\right)=\left(\frac{-3}{p}\right)^e.$$ So the equality is false if $e$ is even and $\left(\frac{−3}{p}\right) = -1$. In your example, $\left(\frac{−3}{25}\right) = 1$. –  TMM Jan 12 '13 at 15:54
@TMM, what is the solution of $y^2\equiv-3\pmod{25}?$ –  lab bhattacharjee Jan 12 '13 at 16:16

If $p>2,$$p^e\mid (x^2-x+1)\iff p^e\mid (2x-1)^2+3$$ So, $$(2x-1)^2\equiv-3\pmod{p^e}$$ Applying Discrete Logarithm w.r.t some primitive root$g\pmod {p^e}$,$2ind_g(2x-1)\equiv ind_g(-3)\pmod{p^{e-1}(p-1)}$as$\phi(p^e)=p^{e-1}(p-1)$Using Linear congruence theorem, the last equation is solvable iff$(2,p-1)\mid ind_g(-3)\iff 2\mid ind_g(-3)$and in that case it has exactly$(2,p-1)=2$solutions. Now we can prove,$-3$is a quadratic residue of$p^e,$iff it is a quadratic residue modulo$p$(See below) So, the number of solutions of $$(2x-1)^2\equiv-3\pmod{p^e}$$ is$0=1-1$or$2=1+1$i.e. is$1+\left(\frac{-3}p\right)$for all prime$p>3$[Proof: Now, if$-3$is a quadratic residue modulo$p^s$so there exists an integer$y$such that$p^s\mid(y^2+3)\implies y^2+3=a\cdot p^s$for some positive integer$a$Now,$(y+b\cdot p^s)^2+3=y^2+3+2y\cdot b\cdot p^s+b^2p^{2s}=a\cdot p^s+2y\cdot b\cdot p^s+b^2p^{2s}$If$p^{s+1}\mid (a\cdot p^s+2y\cdot b\cdot p^s+b^2p^{2s})\iff p\mid (a+2b)$if$2s\ge s+1\iff s\ge 1\implies 2b\equiv-a\pmod p$so if$y^2\equiv-3\pmod{p^s}$is solvable so will be$y^2\equiv-3\pmod{p^{s+1}}$Using induction we say$-3$is a quadratic residue of$p^e$if it is a quadratic residue of$p$for$e>1.$Again if for$e>1,p^e\mid(y^2+3)\implies p\mid (y^2+3),$so if$-3$is a quadratic residue of$p^e,$then it is a quadratic residue modulo$p$So,$-3$is a quadratic residue of$p^e,$iff it is a quadratic residue modulo$p$] - Yes, I know it. But I have to show that$\left(\frac{-3}{p^e}\right)=\left(\frac{-3}{p}\right)$, is there such conclusion? – hxhxhx88 Jan 12 '13 at 15:28 Wonderful proof! Thank you very much! – hxhxhx88 Jan 12 '13 at 15:58 @hxhxhx88, but the indices with respect to different moduli may vary, right?? – lab bhattacharjee Jan 12 '13 at 16:01 What indices?..And I'm still have a problem, why (3) is solvable iff$(2,p-1)|ind_g(-3)$? – hxhxhx88 Jan 12 '13 at 16:03 @hxhxhx88, please have a look into en.wikipedia.org/wiki/Linear_congruence_theorem – lab bhattacharjee Jan 12 '13 at 16:04 There's a much easier solution:$x^2-x+1$is a multiple of$p^e$if and only if$(x^2-x+1)(x+1) = x^3+1$is a multiple of$p^e$and$x\not\equiv1\pmod p$. (Here it is important that$-1$is not a root of$x^2-x+1$, which is true for all primes but 3.) And the congruence$x^3\equiv-1\pmod{p^e}$means that$x^6\equiv1\pmod{p^e}$but$x^3\not\equiv1\pmod p$, which means that$x$has order 6 modulo$p^e$. In other words, the roots of$x^2-x+1$modulo$p^e$are exactly the elements of order 6 modulo$p^e$(for$p\ne3$). Since the multiplicative group modulo$p^e$is cyclic (for$p$odd), the number of such elements is 2 if$6\mid (p^e-1)$and 0 otherwise. Similarly, the roots of the cyclotomic polynomial$\Phi_n(x)$modulo$p^e$are simply the elements of order$n$. The above is the case$n=6$. - There is a typo, it should be$6\mid p^e-1$, anyway, a beautiful proof! Thank you! – hxhxhx88 Jan 13 '13 at 13:27 you're welcome! thanks for catching the typo - fixed – Greg Martin Jan 14 '13 at 4:19 3 is enough instead of$n=6$, since$-x$has order 3 ;) – N. S. Jan 14 '13 at 5:42 Equivalently,$3\mid p^e-1$if and only if$6\mid p^e-1\$. We've reproved the fact that most primes are odd! –  Greg Martin Jan 14 '13 at 21:00