If a prime natural number $p\neq 3$ divides $a^3-3a+1$ for some integer $a$, then $p\equiv \pm1\pmod{9}$. 
$\textbf{Problem:}$  Let $a$ be a positive integer and $p$ a prime divisor of $a^3-3a+1$, with $p \neq 3$. Prove that $p$ is of the form $9k+1$ or $9k-1$, where $k$ is an integer.

I tried to complete the cube which didn't turn out to be anything good.  If the condition asked for $p$ to be only of the form $9k+1$, I would try to show that $a$ has order $9 \pmod{p}$.  But the given condition seems somewhat odd to me.
So, overall I could hardly make any real progress.
Any kind of hint or solutions are appreciated.
 A: Without all details: If $\zeta$ is a primitive $9$th root of unity then $x^3-3x+1$ is the minimal polynomial of $\alpha = \zeta + \zeta^{-1}$. So if $x^3-3x+1$ has a root $\beta \pmod p$ for some prime then $\mathbb F_{p^2}$ has a root of $x^2-\beta x+1$ and if $p \neq 3$ then that root is a primitive $9$th root of unity. That implies that $9 \mid p^2-1$ since $\lvert \mathbb F_{p^2}^{\ast} \rvert = p^2-1$.
A: Let $f(x)=x^3-3x+1$.  Then,
$$g(t):=t^3\,f\left(t+\frac1t\right)=t^3\,\left(\left(t+\frac1t\right)^3-3\left(t+\frac1t\right)+1\right)\,.$$
Hence,
$$g(t)=t^6+t^3+1=\Phi_9(t)\,,$$
where $\Phi_n$ is the  $n$-th cyclotomic polynomial for each positive integer $n$.
Let $p\neq 3$ be a prime natural number.  We work in $\mathbb{F}_p$.  Suppose that $f(a)=0$ for some $a\in\mathbb{F}_p$.  We consider the equation
$$t+\frac{1}{t}=a\,.\tag{*}$$
Suppose that this equation has a solution $t=b$ for some $t\in\mathbb{F}_p\setminus\{0\}$, then $\Phi_9(b)=0$.  As $t^9-1$ is divisible by $\Phi_9(t)$, we conclude that
$$b^9-1=0\,.$$
However,
$$b^{p-1}-1=0$$
as well.  Consequently, if $d=\gcd(9,p-1)$, then
$$b^{d}-1=0\,.$$
It is easily seen that $d\neq 1$ and $d\neq 3$; otherwise $b^3=1$, whence
$$0=\Phi_9(b)=b^6+b^3+1=(b^3)^2+(b^3)+1=1^2+1+1=3\,,$$
contradicting the assumption that $p\neq 3$.  Thus, $d=9$ implying that $9\mid p-1$.
Suppose now that (*) has a solution $t=b$, where $b\in\mathbb{F}_{p^2}\setminus\mathbb{F}_p$.  Since $\Phi_9(b)=0$, we conclude as before that
$$b^9-1=0\,.$$
However, since $b\in\mathbb{F}_{p^2}\setminus\{0\}$, we have
$$b^{p^2-1}-1=0\,.$$
Therefore,
$$b^{d}-1=0\,,$$
where $d:=\gcd(9,p^2-1)$.  Using the same argument as the previous paragraph, $d=1$ and $d=3$ are ruled out.  Therefore, $d=9$, making $9\mid p^2-1=(p-1)(p+1)$.  Since $3$ divides exactly one of the numbers $p-1$ and $p+1$, we conclude that $9\mid p-1$ or $9\mid p+1$, establishing the claim.
Conversely, let $p$ be a prime natural number such that $p\equiv \pm1 \pmod{9}$.  Then, $9\mid p^2-1$.  Therefore, $\Phi_9(t)$ is a factor of $t^{p^2-1}-1$.  Thus, $\Phi_9(t)$ splits into linear factors in $\mathbb{F}_{p^2}$.  Let $b_1,b_2,b_3,b_1^{-1},b_2^{-1},b_3^{-1}$ be the six roots of $\Phi_9(t)$ in $\mathbb{F}_{p^2}\setminus\{0\}$.  Then, the polynomial $f(x)=x^3-3x+1\in\mathbb{F}_p[x]$ has three roots $b_1+b_1^{-1}$, $b_2+b_2^{-1}$, and $b_3+b_3^{-1}$ in $\mathbb{F}_{p^2}$.  Consequently, $f(x)$ cannot be irreducible over $\mathbb{F}_p$.  Ergo, $f(x)$ has a root $a\in\mathbb{F}_p$.  Therefore, we have the following proposition.

Proposition.  Let $p\neq 3$ be a prime natural number.  There exists an integer $a$ such that $a^3-3a+1$ is divisible by $p$ if and only if $p\equiv \pm1\pmod{9}$, or equivalently, $p\equiv \pm1\pmod{18}$.

Remark.  In the case where $p\equiv \pm1\pmod{9}$, it can be easily seen that $f(x)$ has exactly three distinct roots in $\mathbb{F}_p$.  This is because the discriminant of $f(x)$ is $81\not\equiv 0\pmod{p}$, and the roots of $f(x)$ are of the form $a$, $h(a)$, and $h\big(h(a)\big)$ for some $a\in\mathbb{F}_p$, where $h(x):=x^2-2$.  See this related question: Expressing the roots of a cubic as polynomials in one root.
