Legendre symbol $(-3/p)$ where $p = 1 \mod 3$ Suppose $p = 1 \bmod 3$, prove the following statements:


*

*prove that $x^2 + x + 1 = 0 \mod p$ has a solution

*Prove that $\left(\frac{-3}{p}\right) = 1$ if $p = 1\mod 3$

*Determine the discriminant of $x^2 + x + 1$

*Prove using 2,3 that $\left(\frac{-3}{p}\right) = -1$ if $p = -1\mod 3$


This is what I've tried by each question:


*

*prove $x^2 + x = -1 \mod p$ has a solution, i tried to find an x such that: $x^2 + x = a^{\frac{p-1}{2}} = -1 \mod p$, where we use that a is equal to a quadratic non-residue and use Euler. I don't seem to see why this is true though.

*Note the following:
$(2x+1)^2 = 4x^2 + 4x + 4 = 4(x^2 + x + 1) - 3 = -3 \mod p$. So this solution exist and thus $-3$ must be a quadratic residue mod p.

*-3

*?

 A: *

*You will need to use Cauchy's theorem (or similar) as mentioned in the answer that Jack D'Aurizio provided to the question mentioned in his comment. So if $p \equiv 1 \mod 3$ then there is an $x \ne 1$ for which  $x^3 = 1$, and then $(x-1)(x^2+ x+1) =0$ so we have our required root of $x^2 + x + 1 = 0$. By the way, any quadratic equation that has a root will automatically also have a second root, which can be found by noting that $x^2[(x^{-1})^2+x^{-1}+1]=x^2+x+1=0$ and thus $x^{-1}$ is the second root. Alternatively, note that $(-(x+1))^2+-(x+1)+1=x^2+x+1=0$, so the second root is $-(x+1)$, and we find as a bonus that $x^{-1}=-(x+1)$. This of course also follows easily by multiplying $x^2+x+1=0$ by $x^{-1}$.

*Agree with your own answer except for the typo:
$$(2x+1)^2=4x^2+4x+1=4(x^2+x+1)-3=-3$$ so $(\frac{-3}{p})=1$

*Indeed $D=1^2-4\cdot 1\cdot 1 = -3$. Effectively 2. says that $\sqrt{D}$ exists, hence we can find the roots of the equation $x^2+x+1=0$ from $x_{1,2}=\frac{-1 \pm \sqrt{-3}}{2} = \frac{-1 \pm (2x+1)}{2}$, thus $x_1=x$, $x_2=-(x+1)$, as mentioned under 1.

*If $p \equiv -1 \mod 3$ then there will be no non-trivial root of $x^3=1$ (as 3 does not divide the group order $p-1$), thus $\sqrt{-3}$ does not exist (otherwise we would have solutions of $x^2+x+1=0$), which is the same as $(\frac{-3}{p})=-1$
