##### 原根 - 原根 - **原根**是在[[模运算]]特殊的[[整数]]. 对于一个模数 $m$, 如果存在一个整数 $g$ 使得对于所有与 $m$ [[互素]]的整数 $a$, 都存在某个整数 $k$ 使得 $g^k \equiv a \pmod{m}$, 则称 $g$ 是模 $n$ 的原根, 换句话说 $g$ 是模 $n$ 下的一个生成元, 它的幂次可以生成所有模 $n$ 下的单位群元素, 即与 $n$ 互素的数. 如果 $a$ 的[[乘法阶]]等于模 $n$ 的[[欧拉函数]]值 $\text{ord}_n(a) = \varphi(n)$, 那么 $a$ 是模 $n$ 的原根,