阶与原根
Published:
阶
在 $\bmod m$ 下，对于 $a \perp m$，方程
\[a^x \equiv 1 \pmod m\]的最小正整数解称为 $a$ 的阶 (multiplicative order)，记作 $\text{ord}_m(a)$。
阶总是存在吗？
是。因为
\[a^{\varphi(m)} \equiv 1 \pmod m\]$a^x \equiv 1 \pmod m$ 的其它解有什么性质？
考虑对 $\text{ord}_m(a)$ 作带余除法。设 $x = \text{ord}_m(a) q + r$：
\[a^x \equiv (a^{\text{ord}_m(a)})^q \times a^r \equiv a^r \pmod m\] \[a^r \equiv 1 \pmod m\]但是由于 $\text{ord}_m(a)$ 是最小解，$r$ 如果是正整数则不能小于它。因此 $r = 0$。
\[\boxed{ a^x \equiv 1 \pmod m \iff \text{ord}_m(a) \mid x }\]显然推论：
\[\text{ord}_m(a) \mid \varphi(m)\]对于 $a \perp m$，所有的 $a^x$ 在 $\bmod m$ 意义下的乘法构成什么结构？
循环群 $C_{\text{ord}_m(a)}$，与模意义下加法群 $(\mathbb Z / \text{ord}_m(a) \mathbb Z, +)$ 同构。
不难证明
\[\boxed{ a^x \equiv a^y \pmod m \iff x \equiv y \pmod {\text{ord}_m(a)} }\]所以 $\bmod m$ 下的 $a^x$ 与 $\bmod \text{ord}_m(a)$ 下的 $x$ 完全是同构的。
原根
若 $a$ 满足 $\text{ord}_m(a) = \varphi(m)$，则 $a$ 是 $\bmod m$ 下的一个原根 (primitive root)。一般用 $g$ 表示。
原根存在性
模数 $m$ 有原根，当且仅当以下几项有一项成立：
- $m = 1$，如果你愿意。
- $m = 2$
- $m = 4$
- $m$ 是奇质数的幂
- $m$ 是奇质数的幂的 $2$ 倍
证明非常复杂，略去。
一般来说，我们只要知道奇质数必有原根就行了。
原根判定
一个数 $g$ 是 $\bmod m$ 的原根，当且仅当：对于 $\varphi(m)$ 的任意质因子 $p$，都有
\[g^{\frac {\varphi(m)} p} \not \equiv 1 \pmod m\]证明：
只要说明 $\forall d \mid \varphi(m)$ 都有 $g^d \not \equiv 1 \pmod m$ 就行了。进一步地，我们发现所有 $\frac {\varphi(m)} p$ 足以覆盖 $d$ 的倍数。
原根个数
若 $m$ 有原根，则原根个数为
\[\varphi(\varphi(m))\]证明：
假设我们已经找到了一个原根 $g$，那么其余的任意原根 $g^*$ 必定可以表示为
\[g^* \equiv g^k \pmod m\]但是这个 $k$ 必须和 $\varphi(m)$ 互质，否则
\[\text{ord}_m(g^k) = \frac {\varphi(m)} {\gcd(\varphi(m), k)}\]转这么多步就回到 $1$ 了。
而只要和 $\varphi(m)$ 互质的 $k$ 都可以，所以有 $\varphi(\varphi(m))$ 个。
原根密度
对于有原根的数 $m$：
\[\frac {\varphi(\varphi(m))} m = \Omega \left( \frac 1 {\log \log m} \right)\]证明要读论文，略去。
因此随机取数直到取到原根为止，期望次数是 $O(\log \log m)$ 的。
升幂
对于质数 $p$ 和数 $a$（$p \nmid a$），$\text{ord}_{p^k}(a)$ 和 $\text{ord}_p(a)$ 有什么关系？
由于证明需要用 LTE，所以我们对奇质数和 $2$ 分开考虑。
奇质数
对于 $a \ne \pm 1$：令阈值 $k_0 = \nu_p(a^{\text{ord}_p(a)} - 1)$，有
\[\boxed{ \text{ord}_{p^k}(a) = \text{ord}_p(a) \times p^{\max(k - k_0, 0)} }\]证明：
设 $\text{ord}p(a) = d$，$\text{ord}{p^k}(a) = d \times m$。用 LTE 拆：
\[\begin{aligned} \nu_p(a^{dm} - 1) & \ge k \\ \nu_p(a^d - 1) + \nu_p(m) & \ge k \\ \nu_p(m) & \ge k - \nu_p(a^d - 1) \\ m & \ge p^{k - \nu_p(a^d - 1)} \end{aligned}\]证毕。
$p = 2$
若 $a \bmod 4 = 1$ 且 $a \ne 1$：令阈值 $k_0 = \nu_2(a - 1)$，有
\[\boxed{ \text{ord}_{2^k}(a) = 2^{\max(k - k_0, 0)} }\]若 $a \bmod 4 = 3$ 且 $a \ne -1$：令阈值 $k_0 = \nu_2(a + 1)$（注意加号），有
\[\boxed{ \text{ord}_{2^k}(a) = \begin{cases} 1, & k = 1 \\ 2^{\max(k - k_0, 1)}, & \text{otherwise} \\ \end{cases} }\]证明：
对于 $a \bmod 4 = 1$ 的情况，LTE 原版依然适用。
对于 $a \bmod 4 = 3$ 的情况，设 $\text{ord}_{2^k}(a) = m$。
首先应该发现 $2 \mid m$，因为在 $\bmod 4$ 下 $a$ 是 $-1$，只有偶数次方才可能变成 $1$。当然这也意味着 $k = 1$ 需要单独考虑。
\[\begin{aligned} \nu_2(a^m - 1) & \ge k \\ \nu_2(\frac {a^2 - 1} 2) + \nu_2(m) & \ge k \\ \nu_2(m) & \ge k - \nu_2(\frac {a^2 - 1} 2) \\ \nu_2(m) & \ge k - \nu_2(a + 1) \\ \end{aligned}\]与此同时要记得 $\nu_2(m) \ge 1$。得证。