Problem: I am trying to prove that
$$
x^2 + x + 1 \equiv 0 \mod p
$$
has a solution where $p$ is a prime such that $p \equiv 1 \mod 3$, without using quadratic reciprocity. I am also suspecting that it has no solution if $p \equiv -1 \mod 3$.
Attempt: I checked for some small primes and tried rewriting the equation, like
$$
x(x + 1) \equiv -1 \mod p,
$$
and substituting $x$, e.g. $x = y -1$ gives
$$
(y-1)^2 + y-1 + 1 = y^2 – y + 1 \equiv 0 \mod p.
$$
(Using that $\mathbb{F}_p$ is a field this question is equivalent.)
Best Answer
The multiplicative group modulo $p$ has order $p-1$ and is cyclic with some generator $a$. If $p-1=3k$, then $1$, $a^k$, $a^{2k}$ are three distinct roots of $X^3-1$. Divide out $(X-1)$ to obtain that $a^k$, $a^{2k}$ are roots of $X^2+X+1$.
On the other hand, if $p-1$ is not a multiple of $3$, then the cyclic group of order $p-1$ has no element of order $3$, hence $1$ is the only root of $X^3-1$, hence the only candidate as a root fo $X^2+X+1$, which works out only if $p=3$.