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.

I am stuck proving the theorem that there exists $x$, $x^4 \equiv 2 \pmod p$ iff $p$ is of the form $A^2 + 64B^2$.

So far I have got this (and I am not sure if it's correct)


Let $p = a^2 + b^2$ be an odd prime,

  • $\left(\frac{a}{p}\right) = \left(\frac{p}{a}\right) = \left(\frac{a^2 + b^2}{a}\right) = \left(\frac{b^2}{a}\right) = 1$

since $p \equiv 1 \pmod 4$

  • $\left(\frac{a+b}{p}\right) = \left(\frac{(a+b)^2-2ab}{a+b}\right) = \left(\frac{2}{a+b}\right) = (-1)^{((a+b)^2-1)/8}$

using the Jacobi symbol and second supliment of quadratic reciprocity.

  • $(a+b)^{(p-1)/2} = (2ab)^{(p-1)/4}$

since $(a+b)^2 \equiv 2ab \pmod p$


and the last step which I'm stuck on now is for $p = a^2 + b^2$ let $x^2 \equiv -1 \pmod p$ then $2^{(p-1)/4} = x^{ab/2}$. And I don't see how to prove the theorem with this result.

share|improve this question

1 Answer 1

up vote 3 down vote accepted
+100

We can asume that 2 is a quadratic residue mod $p$ and so that $p \equiv 1 \pmod 8$ and this implies that if we pick $a$ odd and $b$ even then $b$ is a multiple of 4. We have to prove that $b$ is a multiple of 8.

First observe thatas $x^2 \equiv -1 \pmod{p}$ and $a^2 + b^2 = p$ we have $$ \left(\frac{a+b}{p}\right) \equiv (-1)^{((a+b)^2-1)/8} \equiv x^{(p+2ab-1)/4} \pmod{p} $$ note that the exponent of $x$ is even because $b$ is multiple of 4, so we can chose the sign of the base as we wish.
In adition we also have $$ a^2 \equiv -b^2 \pmod{p} $$ so $a^2 \equiv (xb)^2 \pmod{p}$ and $$ax \equiv \pm b \pmod{p}$$ and picking the sign of $x$ we can asume that $ax \equiv b \pmod{p}$. So $ab \equiv a^2 x$ and $$ (ab)^{(p-1)/4} = a^{(p-1)/2} x^{(p-1)/4} \equiv x^{(p-1)/4} \pmod{p} $$ because $a$ is a quadratic residue mod $p$.

The identity you obtained: $$\left(\frac{a+b}{p}\right) = (a+b)^{(p-1)/2} \equiv (2ab)^{(p-1)/4} \pmod p $$ now becomes $$x^{(p+2ab-1)/4} \equiv 2^{(p-1)/4} x^{(p-1)/4} \pmod p $$ and in consequence $$2^{(p-1)/4} \equiv x^{ab/2} \pmod p $$ As $b$ is multiple of 4 say $b = 4b'$, we have $$2^{(p-1)/4} \equiv (-1)^{ab'} \pmod p $$ so $2$ is a biquadratic residue iif $b'$ is even or what is the same thing iif $b$ is multiple of 8 and we are done.

share|improve this answer
    
I understood everything except "so 2 is a biquadratic residue iif b′ is even" how does $2^{(p-1)/4}=1$ imply that 2 is a biquadratic residue? Thanks! –  quanta Mar 7 '11 at 23:31
2  
2 is a biquadratic residue if and only if there is an $y$ with $y^4\equiv 2\pmod{p}$ if and only if $2^{(p-1)/4} \equiv (y^4)^{(p-1)/4} \equiv 1 \pmod{p}$ the last iif can be seen for example using a primitive root mod $p$. –  Esteban Crespi Mar 8 '11 at 7:44

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.