Congruence modulo a prime. The goal is to show that $x^2+3\equiv 0 \pmod p$ is solvable for every prime $p$, $p\equiv 1 \pmod 3$.  
What I know so far is that, since $3\mid (p-1)$, $x^3\equiv 1 \pmod p$ has exactly three solutions.  From that you get that $x^3-1\equiv(x-1)(x^2+x+1) \pmod p$ and therefore $x^2+x+1\equiv 0 \pmod p$ must have two solutions since $(x-1)\equiv 0 \pmod p$ has at most one solution.
Is there some step I'm missing here to relate $x^2+x+1$ to $x^2+3$?

This type of problem is commonly solved with Legendre symbols: $\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=(-1)^{\frac{p-1}{2}}(-1)^{\lfloor \frac{p+1}{6} \rfloor}$, which is $1$ if $p\equiv 1,7\pmod{12}$ and $-1$ if $p\equiv 5,11\pmod{12}$.
A more direct approach is to note that $-3$ is the discriminant of $x^2+x+1$, so taking an $x$ that solves $x^2+x+1\equiv 0$ we set $y=2x+1$, and $y^2\equiv -3$.
