原根

阶：

定义：满足同余式 $a^{n} \equiv 1 (\mod m)$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $δ_{m} (a)$ 或 ${ord}_{m} (a) .$

由欧拉定理可知，对 $a \in Z$ ， $m \in N^{*}$ ，若 $(a, m) = 1$ ，则 $a^{φ (m)} \equiv 1 (\mod m)$ .

性质：

$a$ , $a^{2}$ , $\dots$ , $a^{δ_{m} (a)}$ 模 $m$ 两两不同余。

若 $a^{n} \equiv 1 (\mod m)$ ，则 $δ_{m} (a) ∣ n .$

若 $a^{p} \equiv a^{q} (\mod m)$ ，则有 $p \equiv q (\mod δ_{m} (a)) .$

设 $m \in N^{*}$ ， $a$ , $b \in Z$ ， $(a, m) = (b, m) = 1$ ，则

$δ_{m} (a b) = δ_{m} (a) δ_{m} (b)$
的充分必要条件是
$(δ_{m} (a), δ_{m} (b)) = 1$

设 $k \in N$ ， $m \in N^{*}$ ， $a \in Z$ ， $(a, m) = 1$ ，则
$δ_{m} (a^{k}) = \frac{δ_{m} (a)}{(δ_{m} (a), k)}$

原根：

定义：设 $m \in N^{*}$ ， $g \in Z$ . 若 $(g, m) = 1$ ，且 $δ_{m} (g) = φ (m)$ ，则称 $g$ 为模 $m$ 的原根。

即 $g$ 满足
$δ_{m} (g) = | Z_{m}^{*} | = φ (m)$ . 当 $m$ 是质数时，我们有 $g^{i} mod m, 0 < i < m$ 的结果互不相同。

1 原根判定定理:

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

2 原根存在定理:

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