第 4 章：乘法阶与指数的周期

4.1 阶是最小的“回到1”的指数

若 $\gcd(a,n)=1$ ，定义

$d=\operatorname{ord}_n(a) =\min\{k\ge1:a^k\equiv1\pmod n\}.$

这个 $d$ 称为 $a$ 模 $n$ 的乘法阶。它存在，因为欧拉定理已经给出一个符合条件的正指数 $\varphi(n)$ 。定义只是从所有符合条件的正指数中取最小的一个。

例如模7时， $2,2^2,2^3$ 的余数是 $2,4,1$ ，所以 $\operatorname{ord}_7(2)=3$ ；而费马小定理给的指数是6。这里6没有错，它只是没有声称自己最小。

4.2 为什么其他回到1的指数必为阶的倍数

若 $a^m\equiv1$ ，把 $m$ 除以 $d$ ：

$m=qd+r,\qquad0\le r<d.$

因为 $a^d\equiv1$ ，有 $a^m\equiv a^r$ ，所以 $a^r\equiv1$ 。如果 $r>0$ ，它就是一个比 $d$ 更小、还能使幂回到1的正指数，违反 $d$ 的最小性。因此 $r=0$ ，即 $d\mid m$ 。

反过来，如果 $d\mid m$ ， $a^m$ 是 $a^d$ 的整数次幂，当然同余于1。于是对非负整数 $m$ ，

$\boxed{a^m\equiv1\pmod n\quad\Longleftrightarrow\quad d\mid m.}$

把 $m=\varphi(n)$ 代入，得到 $d\mid\varphi(n)$ 。这是比“阶不超过欧拉函数”更强的整除结论，后面的计数需要的是它的整除性。

4.3 对指数取模，为什么不改变幂值的模数

同样把任意非负指数 $k$ 写成 $k=qd+r$ ，有 $a^k\equiv a^r\pmod n$ 。因此幂的值由 $k\bmod d$ 决定。

这里有两个不同的对象： $k$ 是指数，其周期为 $d$ ； $a^k$ 是幂值，仍在模 $n$ 下计算。可以记为

$k\bmod d\quad\longmapsto\quad a^k\bmod n.$

例如 $8$ 模13的阶为4，故 $8^{11}\equiv8^3\equiv5\pmod{13}$ 。指数11对4取余，是在寻找循环中的位置；最后的余数5仍是对13计算出来的。后面从 $p$ 转到 $2^\alpha$ 时，发生的正是这种“指数周期改变”，不是把幂值的模数换掉。

4.4 怎样求阶，以及一个幂的阶

求阶时不必试所有正整数，只需在 $\varphi(n)$ 的因数中找最小满足 $a^d\equiv1$ 的 $d$ 。若已知某个合适的指数 $M$ ，可以逐个尝试移除 $M$ 的质因子；每次都检验移除后的幂是否仍为1。

另一个常用结论是：若 $a$ 的阶为 $d$ ，那么 $a^k$ 的阶为

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

它为什么有这个形状？ $(a^k)^m\equiv1$ 等价于 $d\mid km$ 。写 $d=c d'$ 、 $k=c k'$ ，其中 $c=\gcd(d,k)$ ，则条件变成 $d'\mid k'm$ 。由于 $d',k'$ 互质，等价于 $d'\mid m$ ；最小正 $m$ 就是 $d'$ 。对 $k=0$ ，公式也给出阶1，因为 $a^0=1$ 。