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. ?
  • $\begingroup$ Have a look at this rather famous question: math.stackexchange.com/questions/685958/… $\endgroup$ – Jack D'Aurizio Oct 28 '15 at 14:25
  • 1
    $\begingroup$ 1) makes no sense as written. Also such "question dumps" are not really welcome. $\endgroup$ – quid Oct 28 '15 at 14:30
  • 1
    $\begingroup$ What is $x$? Is it solve for $x$? $\endgroup$ – SchrodingersCat Oct 28 '15 at 14:33
  • $\begingroup$ sorry forgot the sentence has a solution i will edit it right away $\endgroup$ – Kees Til Oct 28 '15 at 14:36
  • 2
    $\begingroup$ 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? $\endgroup$ – André Nicolas Oct 28 '15 at 16:38
  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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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