概念与性质
定义（原根）：
- 设 m 是大于 1 的整数，a 是与 m 互素的整数，若 $$ord_m(a) = \phi(m)$$，则 a 叫做 m 的原根。
定理：
- a 是 m 的原根的充要条件是 $$1, a, a^2, …, a^{\phi(m)-1}$$ 是模 m 的一个缩系。
定理：
设 a 是 m 的一个原根，t 是非负整数，则 $$a^t$$ 也是 m 的原根的充要条件是 $$gcd(t, \phi(m)) = 1$$
若 a 是 m 的原根，则 m 恰有 $$\phi(\phi(m))$$ 个模 m 不同余的原根。
定理：
- 若 p 是奇素数，则 p 的原根存在
定理：
- 设 m 是大于 1 的整数，则 m 的原根存在的充要条件是 m 为 $$2, 4, p^l, 2p^l$$ 之一，其中 $$l \ge 1,$$ p 是奇素数。
定理：
- 设 m 是大于 2 的整数，$$\phi(m)$$ 的所有因子是 $$q_1, q_2, \dots, q_s$$，则与 m 互素的正整数 g 是 m 的一个原根的充要条件是 $$\displaystyle g^{\frac{\phi(m)}{q_i}} \not\equiv 1 \pmod{m}, i = 1, 2, \dots, s$$