ある3次方程式の根をモジュロで出す話

方程式：
$$x^3-3x+1\equiv 0~~\mathrm{mod}~p$$
の根を素数$p$に対して出す話。ただし$p\equiv 1~~\mathrm{mod}~9$とする。
　三角関数の$3$倍角の公式より、
$$\cos 3\theta = 4\cos ^3\theta - 3\cos \theta$$
であるので、
$$ (2\cos \theta)^3 - 3\cdot 2\cos \theta + 1 = 1 + 2\cos 3\theta $$
となる。ここで、
$$\cos 3\theta = -\frac{1}{2},~~~0\leq \theta < 2\pi$$
の解は
$$3\theta=\frac{2\pi}{3},~\frac{8\pi}{3},~\frac{14\pi}{3},~~~~~\theta = \frac{2\pi}{9},~\frac{8\pi}{9},~\frac{14\pi}{9}$$
となる。解は$x=2\cos \theta$の形で得ることができる。それは、
$$x = 2\cos\frac{2\pi}{9},~2\cos\frac{4\pi}{9},~2\cos\frac{8\pi}{9}$$
で与えられる。これらは互いに異なる。
$$\left( \cos\frac{14\pi}{9} = \cos\left(2\pi - \frac{14\pi}{9}\right) = \cos\frac{4\pi}{9}. \right)$$
　これを$1$の$9$乗根で書く。
$$\zeta = e^{2\pi i/9} = \cos\frac{2\pi i}{9} + i\sin\frac{2\pi i}{9}$$
とおくと、
$$ x = \zeta + \zeta^8,~~\zeta^2 + \zeta^7,~~\zeta^4 + \zeta^5 $$
となる。だから、$1$の$9$乗根から解を計算できる。
　そこで、モジュロの場合もこれを適用すればいい。$9$で割って$1$余る素数$p$に対し、モジュロ$p$での$x^3-3x+1\equiv 0~~\mathrm{mod}~p$の解を求めてみる。

モジュロ$37$の例

計算により原始根は$2$である。$1$の$9$乗根は$4$乗元で、$4,8,12,\cdots $乗が$\zeta,\zeta^2,\zeta^3,\cdots$に対応する。$16$を何乗もしてモジュロすればすべて出る。
$$ 1,~~16,~~34,~~26,~~9,~~33,~~10,~~12,~~7 $$
がそれらに当たる。そこでこれらに対し
$$\zeta + \zeta^8,~~\zeta^2+\zeta^7,~~\zeta^4+\zeta^5$$
を計算すると、
$$16+7,~~34+12,~~9+33$$
となって$$23,~9,~5$$を得る。これらは実際に、
$$x^3-3x+1\equiv 0~~\mathrm{mod}~37$$
の解になっている。