# Legendre symbol $(-3/p)$ where $p = 1 \mod 3$

Suppose $p = 1 \bmod 3$, prove the following statements:

1. prove that $x^2 + x + 1 = 0 \mod p$ has a solution
2. Prove that $\left(\frac{-3}{p}\right) = 1$ if $p = 1\mod 3$
3. Determine the discriminant of $x^2 + x + 1$
4. 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:

1. 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.
2. 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. -3
4. ?
• Have a look at this rather famous question: math.stackexchange.com/questions/685958/… – Jack D'Aurizio Oct 28 '15 at 14:25
• 1) makes no sense as written. Also such "question dumps" are not really welcome. – quid Oct 28 '15 at 14:30
• What is $x$? Is it solve for $x$? – SchrodingersCat Oct 28 '15 at 14:33
• sorry forgot the sentence has a solution i will edit it right away – Kees Til Oct 28 '15 at 14:36
• The most straightforward way to evaluate most Legendre symbols $(a/p)$ is by using Quadratic Reciprocity. Is that one of the tools you already have? – André Nicolas Oct 28 '15 at 16:38

## 1 Answer

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

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

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

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