原根

1. 核心定义

在定义原根之前，首先需要定义指数（也称为阶，Order）：

• 指数：设 $m>1$，且 $\gcd (a,m)=1$。使同余式 $a^d\equiv 1(\mathrm{mod}m)$ 成立的最小正整数 $d$，称为 $a$ 对模 $m$ 的指数，记为 $or{d}_m(a)$。
• 原根：如果 $a$ 对模 $m$ 的指数恰好等于 $\phi (m)$（即 $or{d}_m(a)=\phi (m)$），则称 $a$ 是模 $m$ 的原根。****

代数意义

如果模 $m$ 存在原根 $g$，则模 $m$ 的简化剩余系构成一个循环群，且 $g$ 是该群的生成元。 即：$\{g^1,g^2,\dots ,g^{\phi (m)}\}\equiv \{r_1,r_2,\dots ,r_{\phi (m)}\}(\mathrm{mod}m)$。

原根就是那个“能跑满全场”的数，它的幂可以生成模 $m$ 简化剩余系里的所有元素。

2. 存在性定理

1. $2$
2. $4$
3. $p^k$ （$p$ 为奇素数，$k\ge 1$）
4. $2p^k$ （$p$ 为奇素数，$k\ge 1$）

反例：$m=8,12,15,2^k(k\ge 3)$ 等都没有原根。

3. 核心性质

1. 数量公式：如果模 $m$ 存在原根，则它共有 $\phi (\phi (m))$ 个不同的原根。
2. 原根的幂：若 $g$ 是模 $m$ 的原根，则 $g^k$ 也是原根的充要条件是 $\gcd (k,\phi (m))=1$。**
3. 指数整除性：对于任意与 $m$ 互素的 $a$，有 $or{d}_m(a)\mid \phi (m)$。

4. 判定与求解算法

如何判断一个数 $g$ 是否为模 $m$ 的原根？

笨办法：计算 $g^1,g^2,\dots ,g^{\phi (m)-1}$，看是否都不等于 1。

高效办法：

• 找到最小可能周期，也就是 $\frac{\phi (m)}{q_i}$
• 设 $\phi (m)$ 的所有不同素因子为 $q_1,q_2,\dots ,q_k$。
• $g$ 是原根 $⟺$ 对于所有的 $q_i$，都有： $g^{\frac{\phi (m)}{q_i}}\not\equiv 1(\mathrm{mod}m)$

---

示例：求模 41 的原根

1. 计算欧拉函数：$\phi (41)=40$。
2. 分解 $\phi (m)$：$40=2^3\times 5$。素因子为 $q_1=2,q_2=5$。
3. 判定测试：我们需要检验 $g^{40/2}=g^{20}$ 和 $g^{40/5}=g^8$ 是否模 41 同余于 1。
   • 试 $g=2$：$2^8\equiv 10\not\equiv 1$，但 $2^{20}\equiv 1(\mathrm{mod}41)$。❌ 不是原根。
   • 试 $g=6$：
     • $6^8\equiv 10\not\equiv 1(\mathrm{mod}41)$
     • $6^{20}\equiv 40\equiv -1\not\equiv 1(\mathrm{mod}41)$
   • 结论：$6$ 是模 41 的一个原根。
4. 原根总数：$\phi (40)=40(1-1/2)(1-1/5)=16$ 个。

• $\varphi (n)=n\cdot {\prod }_{p|n}\left(1-\frac{1}{p}\right)$