有限域本原多项式的一道证明。

Question

m不是一个素数，证明并不是所有的首一m次不可约多项式都是本原多项式。

Answer 1

若m是一个合数, 则存在GF(p)上的首1的m次不可约多项式, 不是本原多项式.
证明: 设m = qn, 其中q > 1是m的最小质因数. 由m是合数, 有n > 1为m的最大真因数.
GF(p^m)的子域均形如GF(p^k), 其中k为m的约数.
于是GF(p^m)的阶数最大的真子域就是GF(p^n).

考虑r = (p^m-1)/(p^q-1) = (p^(qn)-1)/(p^q-1) = p^(q(n-1))+p^(q(n-2))+...+1为整数.
有r是p^m-1的约数, 且r < p^m-1 (因为p^q-1 > 1).
此外由q ≥ 2, n ≥ 2, 可得q(n-1) ≥ 2n-2 ≥ n, 有r > p^n.

GF(p^m)-{0}关于乘法构成一个p^m-1阶循环群.
r是p^m-1的约数, 于是其中存在r阶元, 设a是GF(p^m)-{0}中的一个r阶元.
可知a不属于GF(p^m)的任意真子域GF(p^k), 否则a的阶数 ≤ p^k-1 ≤ p^n-1 < r.
因此GF(p^m) = GF(p)[a], a的极小多项式f(x)是首1的m次不可约多项式.
但r < p^m-1, a不是GF(p^m)的原根, 故f(x)不是本原多项式.
即存在GF(p)上的首1的m次不可约多项式, 不是本原多项式.

注: 对特征p > 2, 无论m > 1是否素数, r总可取为(p^m-1)/(p-1) < p^m-1.
此时m是合数的条件是不必要的.

Answer 2

m次本原多项式的个数为 \phi(p^m-1)/m, \phi 是欧拉函数。

系数在GF(p^m)上的m次首一多项式的个数为 (p^m)^m = p^(2m).

显然 (p^m)^m = p^(2m) >> \phi(p^m-1)/m ( 可用数学归纳法简单证得), 所以命题得证。