Team selection tests for GMO 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 $(\mathrm{mod}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.