Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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