Способы и обсуждение.
1) Дискриминант / «квадратная формула».
Квадратное сравнение имеет дискриминант $D=1-4=-3$. Формально корни (в поле ${\mathbb{F}}_p$) записываются как
$$x\equiv \frac{-1\pm \sqrt{-3}}{2}(\mathrm{mod}p).$$ Следовательно корни существуют тогда и только тогда, когда $-3$ — квадрат по модулю $p$, т.е. когда символ Лежандра $\left(\frac{-3}{p}\right)=1$. Для $p\ne 3$ по квадратичной взаимности
$$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=(-1{)}^{\frac{p-1}{2}}\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right),$$ так что $-3$ квадратичен мод $p$ тогда и только тогда, когда $p\equiv 1(\mathrm{mod}3)$. Следствие:
- $p\equiv 1(\mathrm{mod}3)$ $\Rightarrow$ два различных корня (в ${\mathbb{F}}_p$);
- $p\equiv 2(\mathrm{mod}3)$ $\Rightarrow$ нет корней.
2) Факторизация / группа единиц.
Имеем тождество
$$x^3-1=(x-1)(x^2+x+1).$$ Поэтому $x^2+x+1\equiv 0(\mathrm{mod}p)$ равносильно $x^3\equiv 1(\mathrm{mod}p)$ при $x\not\equiv 1$. В мультипликативной группе ${\mathbb{F}}_p^{\ast }$ (которая циклическая порядка $p-1$) элементы порядка $3$ существуют тогда и только тогда, когда $3\mid (p-1)$, т.е. когда $p\equiv 1(\mathrm{mod}3)$. Тогда таких элементов ровно $2$ (два ненулевых корня). Если $p\equiv 2(\mathrm{mod}3)$, элементом порядка $3$ быть не может и нет корней. Случай $p=3$ отдельный (см. ниже).
3) Через первообразный корень.
Если $g$ — примитивный корень по модулю $p$ и $p\equiv 1(\mathrm{mod}3)$, то решения равны
$$x\equiv g^{\frac{p-1}{3}}\text{и}x\equiv g^{\frac{2(p-1)}{3}}.$$
4) Частный случай $p=3$.
Для $p=3$ дискриминант $-3\equiv 0(\mathrm{mod}3)$, сравнение даёт единственный корень (двукратный) $x\equiv 1(\mathrm{mod}3)$ (проверка: $1^2+1+1\equiv 0$).
Короткое резюме:
- $p=3$: единственный (двойной) корень $x\equiv 1$.
- $p\equiv 1(\mathrm{mod}3)$: ровно два различных корня (элементы порядка $3$ в ${\mathbb{F}}_p^{\ast }$); явные формулы см. выше.
- $p\equiv 2(\mathrm{mod}3)$: решений нет.
Пример: $p=7$ ($7\equiv 1(\mathrm{mod}3)$). Дискриминант $-3\equiv 4$, $\sqrt{4}\equiv \pm 2$, получаем
$$x\equiv \frac{-1\pm 2}{2}(\mathrm{mod}7)\Rightarrow x\equiv 4,2,$$ и действительно $2^3\equiv 4^3\equiv 1(\mathrm{mod}7)$.