$\LARGE{阶的定义}$

对于给定的 $a\in Z, m\in N^*$ ，有 $(a, m) = 1$

满足同余式 $a^n \equiv 1(\bmod m)$ 的最小正整数 $n$ 被称为 $a$ 模 $m$ 的阶，记作 $\delta_m(a) $ 或 $ord_m(a)$。

$\LARGE{阶的性质}$

性质1

$a, a^2 , … a^{\delta_m(a)}$ 模 $m$ 两两不同余

假设存在 $0\leq i,j \leq \delta_m(a)$ 满足 $a^i \equiv a^j (\bmod m)$

那么 $a^{|i - j|} \equiv 1 (\bmod m)$ 与阶的定义矛盾，故假设不成立。

性质2

若 $a^n \equiv 1(\bmod m)$ ，那么 $\delta_m(a) | n$

设 $n = q\delta_m(a) + r (0\leq r < \delta_m(a))$

那么 $a_r \equiv a_r (a^{\delta_m(a)})^q \equiv 1 (\bmod m)$

若 $r > 0$ ，则与阶的定义不符，故 $r = 0$ 。

性质3

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

$\delta_m(ab) = \delta_m(a) \delta_m(b)$ 当且仅当 $(\delta_m(a), \delta_m(b)) = 1$

必要性：

易得 $a^{[\delta_m(a), \delta_m(b)]} \equiv 1 (\bmod m)$ 及 $b^{[\delta_m(a), \delta_m(b)]} \equiv 1 (\bmod m)$

则 $(ab)^{[\delta_m(a), \delta_m(b)]} \equiv 1(\bmod m)$

由 性质2 得

$$\delta_m(ab) | [\delta_m(a), \delta_m(b)]$$

由于 $\delta_m(ab) = \delta_m(a) \delta_m(b)$

故 $ \delta_m(a) \delta_m(b) | [\delta_m(a), \delta_m(b)] , (\delta_m(a), \delta_m(b)) = 1$

充分性：

由 $(ab)^{\delta_m(ab)} \equiv 1 (\bmod m)$ 得

$a^{\delta_m(ab)\delta_m(b)} \equiv (ab)^{\delta_m(ab)\delta_m(b)} \equiv 1(\bmod m)$

则 $\delta_m(a) | \delta_m(ab)\delta_m(b)$ ，结合 $(\delta_m(a), \delta_m(b)) = 1$ 得

$$\delta_m(a) | \delta_m(ab)$$

相对应地，有

$$\delta_m(b) | \delta_m(ab)$$

得到

$$\delta_m(a) \delta_m(b) | \delta_m(ab)$$

又因为

$$(ab)^{\delta_m(a) \delta_m(b)} \equiv 1(\bmod m)$$

所以

$$\delta_m(ab) | \delta_m(a) \delta_m(b)$$

故 $\delta_m(ab) = \delta_m(a) \delta_m(b)$

性质4

设 $k\in N, m \in N^*, a\in Z, (a,m)=1$ ，则有

$$\delta_m(a^k) = \frac{\delta_m(a)}{(\delta_m(a), k)}$$

$a^{k\delta_m(a^k)} \equiv (a^k)^{\delta_m(a^k)} \equiv 1(\bmod m)$

$\Rightarrow \frac{\delta_m(a)}{(\delta_m(a), k)} | \delta_m(a^k)$

$(a^k)^{\frac{\delta_m(a)}{(\delta_m(a), k)}} \equiv (a^{\delta_m(a)})^{\frac{k}{(\delta_m(a), k)}} \equiv 1(\bmod m)$

$\Rightarrow \delta_m(a^k) | \frac{\delta_m(a)}{(\delta_m(a), k)}$

综上所述， $\delta_m(a^k) = \frac{\delta_m(a)}{(\delta_m(a), k)}$

$\LARGE{原根}$

若正整数 $g$ 满足 $g$ 模 $m$ 的阶等于 $\varphi(m)$ ，则 $g$ 为 $m$ 的原根。