有限体上の代数方程式を四則演算とべき根で解こう

原理的には解けるはず

X^2 + X + 1 = 0

>>2
まず、Fq内に根を持つ場合とそうでない場合に分ける。

Fqの標数が3なら、
X^2 + X + 1 = X^2 - 2X + 1 = (X - 1)^2
だからFq内で解ける。解はX = 1 (重解)。

標数が3でない場合。
(X - 1)(X^2 + X + 1) = X^3 - 1
だから、X^2 + X + 1の根は1の原始3乗根。
Fq^×は位数q-1の巡回群だから、位数3の元を含むための条件は、
q - 1 ≡ 0 (mod 3)。

以上から、q ≡ 0, 1 (mod 3)のときは、Fq内で解ける。

q ≡ 2 (mod 3)のとき。
標数が2でないときは、通常と同じくX = (-1 ±√-3)/2。
標数2のときは、一つの根をωとおくと、X = ω, ω^q

X^3 + X + 1 = 0

X^(p^n)−X=0 (mod p)

四則演算だけで完結する: 実数と異なり、有限体では加減乗除（ゼロ除算を除く）がすべてその有限体内で閉じているため、ルート（べき根）を新しく持ち出さなくても、四則演算や累乗の操作だけで解を計算・記述できます。

アホか

X^5 + X + 1 = 0

アルティン・シュライアー

有限体は無限体とは異なり、体に属する要素の数が有限個なので、
1つずつ代入してみて代数方程式を満足するかを確かめていけば、
解のあるなしや何が解であるのかを完全に決定することができます。
全ての解を求めるために掛かる手間は常に有限になります。

既約かどうか判定するには

可能性のある1次因子は有限個、2次因子も有限個、3次因子も有限個、。。。。
だから、それらで順番に割っていけば、可約ならその因子が見つかるし、
半分の次数までの因子をすべて試して割り切れなければ、既約。
割って次数の下がった因子についても同じことを適用すれば完全既約分解できよう。
（これは有限の手間で計算が可能であることを示しているだけで効率は全く度外視
しています。）

メビウス関数

で数えられるのかも