, 2018

Note that the existence of an govern integer as described in the problem can be equivalently stated as follows: the polynomial $x^{3}-3x+1$ has a root in $\mathbb{F}_{p}$. Following the classical method for solving cubic equations, we set $x = w + \frac{1}{w}$. Then
$$x^{3}-3x+1 = \left(w + \frac{1}{w}\right)^{3} - 3\left(w + \frac{1}{w}\right) + 1 = w^{3} + \frac{1}{w^{3}} + 1$$
We then observe that the solutions of the equation $\lambda + \frac{1}{\lambda} + 1 = 0$ are cubic roots of unity. If $p = 9k + 1$ and $g$ is a primitive root $(\bmod\ p)$, then $g^{3k}$ is a cubic root of unity in $\mathbb{F}_{p}$. Thus we look for $w$ such that $w^{3} = g^{3k}$, so we let $w = g^{k}$.
It is now easy to verify that $x = w + \frac{1}{w} = g^{k} + g^{8k}$ is a root of the original cubic polynomial.