概念

设 a 和 m 互质，我们把满足 a^f \equiv 1 \pmod m 的最小正整数 f 称为 a 模 m 的阶或幂（exponent），记作 \delta_m(a) 或 \operatorname{ord}_m(a)。

由 Euler 定理知 a^{\varphi(m)} \equiv 1 \pmod{m}，因此 f 一定为 \varphi(m) 的因数。当 f 取到最大值，即 f = \varphi(m) 时，称 a 是 m 的一个原根（primitive root）。

性质

全部原根

设 g 是 m 的一个原根，t 是一个整数，且 (t, \varphi(m)) = 1，则 g^t 也是 m 的一个原根。若 (t, \varphi(m)) = d > 1，则 g^t 的 \varphi(m) / d 次幂已经等于 1，此时 g^t 不为原根。

因此，设 (t, \varphi(m)) = 1，g^t 是 m 的全部原根。

若 m 存在原根，则 m 有 \varphi(\varphi(m)) 个原根。

原根存在定理

一个模数 m 存在原根，当且仅当 m = 2, 4, p^{\alpha}, 2 p^{\alpha}，其中 p 是一个奇素数，\alpha \in \mathbb{Z}^+。