$x^2+3$ has two zeros over ${\Bbb F}_p$ provided that $x^2+x+1\in{\Bbb F}_p[x]$ has two?

Question

The following is an exercise in abstract algebra:

If $p=1\pmod{3}$, then $x^2+x+1\in\Bbb{F}_p[x]$ has two zeros. Prove in this case that $-3$ is a quadratic residue mod $p$.

---

Showing that $(x^2+x+1)\mid (x^p-x)$, one can get the first part done. But I don't see how the second part, namely, $x^2+3\in\Bbb{F}_p[x]$ has two zeros, can be deduced from the first one. Could one come up with some hints of how to get the first part? (I was thinking one might relate $x^2+3$ to $x^2+x+1$ to make an argument about the zeros of $x^2+3$. But I don't see how I can go on.)

Answer 1

Complete the square. We have $x^2+x+1\equiv 0\pmod{p}$ iff $4x^2+4x+4\equiv 0\pmod{p}$ iff $(2x+1)^2\equiv -3\pmod{p}$.

Remark: Let $F$ be any field that has characteristic $\ne 2$. Then we can make precisely the same argument: We have $x^2+x+1=0$ if and only if $4x^2+4x+4=0$ if and only if $(2x+1)^2=-3$. So if $x^2+x+1=0$ has a solution, then $w^2=-3$ has a solution. And if $w^2=-3$, then by solving $2x+1=w$ we obtain a solution of $x^2+x+1=0$.

Answer 2

The motivation is that $\sqrt{-3}$ is a root of the first and the second has roots ${-1\pm\sqrt{-3}\over 2}$, where these are understood in the more general sense of finite field elements, since the quadratic formula works for any field of characteristic not $2$.

But then it is clear how to get the roots of the second from the first, we can assume $p>3$ from the condition, so that we have that $2^{-1}$ exists in the field, hence we just note that if $\zeta_1,\zeta_2$ are the roots of $x^2+x+1$ we have that $2\zeta_i+1$ are the two roots to $x^2+3$, in other words they are the two things which square to $-3$, proving it is a quadratic residue. You can check this directly as well, even if you don't believe the intuition from the classical quadratic formula, just letting the $\zeta_i$ to be the roots of $x^2+x+1$ we have

$$(2\zeta_i+1)^2+3=4\zeta_i^2+4\zeta_i+1+3=4(\zeta_i^2+\zeta_i+1)=4\cdot 0=0.$$

Answer 3

The map $f\colon x\mapsto 2x+1$ maps roots of $x^2+x+1$ to roots of $x^2+3$. Indeed, $$f(x)^2+3=(2x+1)^2+3=4(x^2+x+1)=0$$ whenever $x^2+x+1=0$.

On the other hand, if $2$ is invertible, then the map $g\colon x\mapsto \frac12(x-1)$ maps roots of $x^2+3$ to roots of $x^2+x+1$. Indeed, $$g(x)^2+g(x)+1=\frac14(x-1)^2+\frac12(x-1)+1=\frac14(x^2+3)=0$$ whenever $x^2+3=0$. Since $f$ and $g$ are inverse maps (if $2$ is invertible), they show that the sets of roots of $x^2+3$ and $x^2+x+1$ are in bijection, hence of the same cardinality.

Of course, the claim is trivially true for $\mathbb F_2$ (though it would be wrong for $\mathbb F_4$, which has two roots of $2^2+x+1$ and only one root of $x^2+3$)