指数
定义
$m > 1 \in Z, \; (a, m) = 1 $，则使得 $a^e \equiv 1 \quad (mod \; m)$ 成立的最小正整数 $e$ 称为 $a$ 对模 $m$ 的指数或者阶，记作 $ord_m a$，若 $\psi(m) = ord_m a$，则 $a$ 称为模 $m$ 的原根
性质
注：$m > 1 \in Z, \; (a, m) = 1$
$a^d \equiv 1 \quad (mod \; m) \iff ord_m a | d$
- 取 $d = \psi(m)$ 可知原根必然是欧拉函数 $\psi(m)$ 的因数
$a \equiv b \quad (mod \; m) \implies ord_m a = ord_m b$
$ord_m a^{-1} = ord_m a$
$a^i, \quad i \in [0, ord_m (a) - 1]$ 两两不同余：
- 若 $a$ 是模 $m$ 的原根，则其构成模 $m$ 的一个简化剩余系
$a^d \equiv a^k \quad (mod \; m) \iff d \equiv k \quad (mod \; ord_m a)$
$ord_m a^d = \cfrac{ord_m a}{(d, ord_m a)}$
- $g^d$ 是模 $m$ 的原根当且仅当 $(d, \psi(m)) = 1$，此定理可用来求一个数的所有原根
- 模 $m$ 的原根个数为 $\psi(\psi(m))$ 或 $0$
- $k | ord_m a$，则使得 $ord_m a^d = k$ 的 $d$ 满足 $\cfrac{ord_m a}{k} | d$，且这样的 $d$ 有 $\psi(k)$ 个
$a, b$ 都与 $m$ 互素，则 $(ord_m a, ord_m b) = 1 \iff ord_m(ab) = ord_m (a) \cdot ord_m (b)$
$n | m \implies ord_n a | ord_m a$
$(m, n) = 1 \implies ord_{mn} a = [ord_m a, ord_n a]$
- 若 $m$ 的标准分解式为 $m = 2^n \cdot p_1^{\alpha_1} \cdots p_k^{\alpha_k}$，则
$$
ord_m a = [ord_{2^n} a, \dots, ord_{p^{\alpha_k}_k} a]
$$$(m, n) = 1$，则对于与 $mn$ 互素的任意整数 $a_1, a_2$，满足
$$
ord_{mn} a = [ord_m a_1, ord_m a_2]
$$
的整数 $a$ 是同余式
$$
\begin{cases}
x \equiv a_1 \quad (mod \; m) \\
x \equiv a_2 \quad (mod \; n)
\end{cases}
$$
的解 $x \equiv a \quad (mod \; mn)$
- 与 $m$ 互素的任意整数 $a, b$，存在整数 $c$，使得
$$
ord_m c = [ord_m a, ord_m b]
$$
该定理可以用于找原根，例如
- $a_i, \quad i \in [1, \psi(m)]$ 是模 $m$ 的简化剩余系，$e$ 是使得 $a_i^e \equiv 1 \quad (mod \; m)$ 成立的最小正整数，则存在整数 $a$，使得，其中 $e$ 称为模 $m$ 的简化剩余系指数
$$
e = ord_m a = [ord_m a_1, ord_m a_2, \dots, ord_m a_{\psi(m)}]
$$
原根的存在性
模 $p$ 原根
设 $p$ 是奇素数，则模 $p$ 的原根存在，且有 $\psi(p-1)$ 个原根
事实上：若 $p$ 是奇素数，$d | p-1$，则模 $p$ 指数为 $d$ 的原根存在
原根的构造方法
设 $p$ 为奇素数，$p-1$ 的所有不同素因数是 $q_1, \dots , q_s$，则 $g$ 是模 $p$ 的原根等价于
$$
g^{(p-1)/q_i} \neq 1 \quad (mod \; p)
$$
性质
- $g$ 是模 $p$ 的一个原根，则 $g$ 或者 $g+p$ 是模 $p^2$ 原根
- $g$ 是模 $p, p^2$ 的原根，则 $g$ 是模 $p^{\alpha}$ 原根
- $g$ 是模 $p^{\alpha}$ 的一个原根，则 $g, g+p^{\alpha}$ 中的奇数是模 $2 p^{\alpha}$ 原根
设 $p$ 为奇素数，则 $m$ 原根存在的充要条件是：$m = 2, 4, p^{\alpha}, 2p^{\alpha}$
指标
定义
$m > 1 \in Z$，$g$ 是模 $m$ 的一个原根，$(a, m) = 1$，则存在唯一的整数 $r$，使得
$$
g^r \equiv a \quad (mod \; m) \quad 1 < r < \psi(m)
$$
$r$ 叫做以 $g$ 为底的 $a$ 对模 $m$ 的一个指标，记作 $r = ind_g a$ 或者 $r = ind \; a$
性质
$m > 1 \in Z$，$g$ 是模 $m$ 的一个原根，$(a, m) = 1$
$r \in Z$ ，$g^r \equiv a \quad (mod \; m) \iff r\equiv ind_g a \quad (mod \; \psi(m))$
$(a_i, m) = 1$，则
$$
ind_g(a_1a_2 \cdots a_n) \equiv ind_g a_1 + ind_g a_2 + \cdots + ind_g a_n \quad (mod \; \psi(m))
$$
n 次同余式
定理一： $m > 1 \in Z$，$g$ 是模 $m$ 的一个原根，$(a, m) = 1$，则
$$
x^n \equiv a \quad (mod \; m)
$$
有解的充分必要条件是
$$
(n, \psi(m)) | ind_g a
$$
且若有解，则解数为 $(n, \psi(m))$
例题：求解同余式 $x^{12} \equiv 37 \quad (mod \; 41)$
由 $(12, 40) = 4 | ind_{41} 37 = 32$，故有解
由性质一知原方程等价于求解
$$
12 ind_{41} x \equiv ind_{41} 37 \equiv (mod \; \psi(41))
$$
即
$$
3 ind_{41} x \equiv 8 \quad (mod \; 10)
$$
即
$$
ind_{41} x \equiv 6 \quad (mod \; 10)
$$
即
$$
ind_{41} x \equiv 6, 16, 26, 36 \quad (mod \; 40)
$$
故
$$
x \equiv 39, 18, 2, 23 \quad (mod \; 41)
$$
