第 15 章：补充证明：质数为什么一定有原根

返回目录

第5章已经说明原根的定义和存在性证明的路线。这一章只解决存在性与相关阶公式，适合想追问“每个质数为什么都能找到这样的底数”时阅读。证明先准备两个工具，再限制多项式的根数，最后逐个拼出所需的质数幂周期。

15.1 辅助引理一：一个幂的阶

若 $a$ 的阶为 $d$ ， $m\ge0$ ，则

$\boxed{\operatorname{ord}_n(a^m)=\frac d{\gcd(d,m)}}.$

先设 $m\ge1$ 。令 $h=\gcd(d,m)$ ，写 $d=hd'$ 、 $m=hm'$ ，其中 $\gcd(d',m')=1$ 。对正整数 $k$ ，

$(a^m)^k\equiv1 \ \Longleftrightarrow\ d\mid mk \ \Longleftrightarrow\ d'\mid m'k \ \Longleftrightarrow\ d'\mid k.$

最后一步用互质消去律。所以最小正 $k$ 是 $d'$ 。当 $m=0$ 时， $a^0$ 的阶为 $1$ ，右边也是 $d/\gcd(d,0)=1$ 。这补全了原对话原根证明中直接使用的公式，也覆盖后面循环群计数的单位元。

15.2 辅助引理二：阶互质时乘积的阶

设 $\operatorname{ord}_n(a)=r$ 、 $\operatorname{ord}_n(b)=s$ ，且 $\gcd(r,s)=1$ 。模整数的乘法可交换，因此

$\boxed{\operatorname{ord}_n(ab)=rs}.$

先有 $(ab)^{rs}=(a^r)^s(b^s)^r\equiv1$ ，故 $t=\operatorname{ord}_n(ab)$ 整除 $rs$ 。

又 $(ab)^t\equiv1$ 。取 $r$ 次幂，得到 $a^{rt}b^{rt}\equiv1$ 。 $a^{rt}\equiv1$ ，所以 $b^{rt}\equiv1$ ，进而 $s\mid rt$ 。由 $r,s$ 互质，推出 $s\mid t$ 。同理 $r\mid t$ ，再由互质乘积整除推论， $rs\mid t$ 。结合 $t\mid rs$ ，得 $t=rs$ 。

这样无需使用负指数也能完成证明。在一般群中还必须要求两个元素可交换，否则幂不一定可拆开。

若阶不互质，结论未必成立：模 $7$ 时 $2,4$ 的阶均为 $3$ ，但 $2\cdot4\equiv1$ ，乘积的阶为 $1$ 。

对任意互质于模数的 $a,b$ ，令 $L=\operatorname{lcm}(r,s)$ ，则 $(ab)^L\equiv1$ ，故乘积的阶总整除 $L$ 。互质阶条件保证这个整除进一步达到等号。

15.3 为什么非零多项式的根数不超过次数

在模质数 $p$ 的系数运算中，设 $f$ 的次数为 $m$ ，最高次系数模 $p$ 不为 $0$ 。它最多有 $m$ 个不同剩余类的根。

先证明因式分解的依据。对每个 $j\ge1$ ，

$x^j-r^j=(x-r)(x^{j-1}+x^{j-2}r+\cdots+r^{j-1}).$

逐项相加给出 $f(x)-f(r)=(x-r)h(x)$ 。若 $f(r)\equiv0$ ，便在模 $p$ 的多项式环里得到 $f(x)=(x-r)h(x)$ ， $h$ 次数为 $m-1$ 。

$m=0$ 时非零常数没有根。归纳地，若没有根结论显然；若有根 $r$ ，对另一个不同根 $s$ ，有 $(s-r)h(s)\equiv0$ 。因为 $p$ 质数且 $s-r\not\equiv0$ ，可消去 $s-r$ ，故 $h(s)\equiv0$ 。归纳假设使其他根最多 $m-1$ 个，加上 $r$ 至多 $m$ 个。证毕。