原根理论

阶

满足同余式 $a^n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 的最小正整数 $n$ 称作 $a$ 模 $m$ 的 阶，记作 ${\delta }_m(a)$ 或 ${\mathrm{ord}}_m(a)$.

详见 阶 词条.

原根

设 $m\in {\mathbf{N}}^{\ast }$，$g\in \mathbf{Z}$. 若 $(g,m)=1$，且 ${\delta }_m(g)=\phi (m)$，则称 $g$ 为模 $m$ 的 原根.

即 $g$ 满足 ${\delta }_m(g)=\left|{\mathbf{Z}}_m^{\ast }\right|=\phi (m)$.

当 $m$ 是质数时，我们有 $g^i\mathrm{m}\mathrm{o}\mathrm{d}m,0<i<m$ 的结果互不相同.

原根是循环群的生成元

在抽象代数中，原根就是循环群的生成元. 这个概念只在模 $m$ 缩剩余系关于乘法形成的群中有「原根」这个名字，在一般的循环群中都称作「生成元」.

并非每个模 $m$ 缩剩余系关于乘法形成的群都是循环群，存在原根就表明它同构于循环群，如果不存在原根就表明不同构.

原根判定定理

计算阶

设 $m\in {\mathbf{N}}^{\ast }$，$g\in \mathbf{Z}$. 若 $(g,m)=1$，且 ${\delta }_m(g)=\phi (m)$，则称 $g$ 为模 $m$ 的原根.

此方法需要计算 $g^1$ 到 $g^{\phi (m)}$，比较低效.

计算每个素因数次方是否均不为 1

设 $m⩾3,(g,m)=1$，则 $g$ 是模 $m$ 的原根的充要条件是，对于 $\phi (m)$ 的每个素因数 $p$，都有 $g^{\frac{\phi (m)}{p}}\not\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$.

原根个数

若一个数 $m$ 有原根，则它原根的个数为 $\phi (\phi (m))$.

特别地：若 $p$ 为素数，那么它有 $\phi (p-1)$ 个原根.

原根存在定理

一个数 $m$ 存在原根当且仅当 $m=2,4,p^{\alpha },2p^{\alpha }$，其中 $p$ 为奇素数，$\alpha \in {\mathbf{N}}^{\ast }$.

原根的合成

模 $mn$ 的原根 $g_{mn}$ 可以由 $m$ 和 $n$ 的原根 $g_m$ 和 $g_n$ 快速得到.

$$\{\begin{array}{l}{g}_{mn}\equiv g_m(\mathrm{m}\mathrm{o}\mathrm{d}m)\\ g_{mn}\equiv g_n(\mathrm{m}\mathrm{o}\mathrm{d}n)\end{array}$$

例如已知 13 的原根为 2，求 26 的原根.

$$\{\begin{array}{l}{g}_{26}\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}13)\\ g_{26}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)\end{array}$$

由中国剩余定理得到 $g_{26}\equiv 15(\mathrm{m}\mathrm{o}\mathrm{d}26)$.

参考

https://oi-wiki.org/math/number-theory/primitive-root/
https://zh.wikipedia.org/wiki/原根