原根

定义

满足 $\gcd (g,m)=1$ 并且 $g$ 的阶为 $\phi (m)$ 的数 $g$ 是模 $m$ 的原根。

原根存在定理

一个数 $m$ 存在原根当且仅当 $m=2,4,p^n,2p^n$，其中 $p$ 为奇素数。

原根判定定理

$g$ 为模 $m$ 的原根的充要条件是：则对于 $\phi (m)$ 的任意质因子 $p$ 有

$$g^{\phi (m)/p}\not\equiv 1\mathrm{mod}m.$$

求原根

• 模 $m$ 的最小原根是 $O\left(m^{\frac{1}{4}}\right)$ 级别的；
• 可以在 $[2,m-1]$ 范围内随机找原根。

如果已经求出一个原根，则对于所有满足 $\gcd (x,\phi (m))=1$ 的 $x$，$g^x$ 都是原根。并且这些就是所有的原根。