# Find $a$ with $a^2-a\equiv -1\pmod p$ when $p$ is a prime with $p\equiv 1\pmod 3$

I'm trying to prove that the primes with form $3k+1$ are not Eisenstein prime. This step: to find $a$ such that $a^2-a\equiv -1\pmod p$ when $p$ is a prime with $p\equiv 1\pmod 3$ is the only obstacle now, and I have thought of many methods, but none of them work.

I know that when proving prime of form $p=4n+1$ aren't Gaussian primes, we need $a$ such that $a^2 \equiv -1\pmod p$. This can be obtained by Wilson's theorem, that $(4n)!\equiv -1\pmod p$, which gives $(4n)!\equiv(1\times 2\times \cdots \times(2n))((-2n)\times\cdots\times(-2)\times(-1))=(1\times 2\times \cdots \times(2n))^2\pmod p$. And this constructs the $a$ we want.

But in this case, things are different. I've tried via mathematica, that the $(3k)!$ or $(6m)!$ cannot be factorized into $a(a-1)$. Such as $720=24\times30$. But when I minus some multiple of the primes, it becomes $24\times 23\equiv-1(\mod 7)$. This special case can't give me more details. So I wonder if there is some method to find $a$ or prove existence without finding it? Only hints are needed! Thanks!

-
$$a^2-a\equiv-1\pmod p\iff (2a-1)^2\equiv-3\pmod p\implies \left(\frac{-3}p\right)=1$$ Check here (qbyte.org/puzzles/p149s.html) when $-3$ is a QR of $p$ – lab bhattacharjee Oct 15 '13 at 14:55
Solving $a^2-a\equiv -1\bmod p$ by the quadratic equation leads to the consideration of whether $-3$ is a quadratic residue $\bmod p$. What is the Legendre symbol $(-3|p)$? – lhf Oct 15 '13 at 14:55

If $p \equiv 1 \bmod 3$, then you can form the polynomial $X^{(p-1)/3} - 1$ which has the zero $1$. Therefore, in $F_p$, $$X-1 \mid X^{(p-1)/3} - 1 \; \Rightarrow \; X^3 - 1 \mid X^{p-1} - 1.$$ On the other hand, $X^{p-1}-1$ decomposes as $(X-1) \cdot (X-2) \cdot ... \cdot (X-(p-1))$ by Fermat's little theorem.
Therefore $X^3 - 1$ splits into linear factors. Since $X^2 + X + 1$ divides $X^3 - 1$, it also splits into linear factors $X^2 + X + 1 = (X-a)(X-b)$. This gives you your $a$.
We know $Y^3-1 = (Y-1)(Y^2-Y+1)$. Since $Y^3-1$ divides $Y^{p-1}-1$, it must have three distinct roots. Two of those roots must be roots of $Y^2-Y+1$.