指数、原根及基本性质

定义

1. 设 $m>1$ 是整数，$a$ 是与 $m$ 互素的正整数，则使得 $a^e\equiv 1 \pmod p$ 成立的最小整数 $e$ 叫做 $a$ 对模 $m$ 的指数，记作 $ord_m(a)$，或者称为阶。

2. 如果 $\varphi(m)= e$，则称 $a$ 为模 $m$ 的原根。

3. 如果 $a$ 是模 $m$ 的原根，则模 $m$ 的即约剩余系 由 $a$ 的方幂组成，即模 $m$ 的即约剩余系为循环群。

定理

1. 设 $\gcd(a,m)=1$，则 $a^0,a^1,\cdots,a^{ord_m(a)-1} \pmod m$ 两两不同余。特别的当 $a$ 为模 $m$ 的原根，上述数组为模 $m$ 的简化剩余系。

2. 设 $\gcd(a,m)=1$，则整数 $d$ 使得 $a^d\equiv1 \pmod p$ 的充要条件是 $ord_m(a)\mid d$

3. 设 $m>1$ 是整数，$a$ 是与 $m$ 互素的整数，则 $ord_m(a)\mid \varphi(m)$

4. 设 $\gcd(a,m)=1$，则 $a^d\equiv a^k \pmod m \lrArr d\equiv k \pmod{ord_m(a)}$

5. 设 $\gcd(a,m)=1$，设 $d\ge 0$ 为整数，则 $ord_m(a^d)=\cfrac{ord_m(a)}{\gcd(ord_m(a),d)}$

性质

前提：$\gcd(a,m)=1$

1. $b\equiv a \pmod p$，则 $ord_m(b) = ord_m(a)$
2. 设 $a^{-1}a\equiv 1 \pmod p$，则 $ord_m(a)=ord_m(a^{-1})$

先假设 $a$ 的 $ord_m(a)$ 序列，$b$ 有一个与其相对应的序列。根据两个序列的关系，即可证明。

存在原根的模数

存在定理

1. 模 $m$ 的原根存在仅当 $m=2,4,p^\alpha,2p^\alpha$，其中 $p$ 为奇素数。

2. 设 $\gcd(ab,m)=1,\gcd(a,b)=1$，如果 $\gcd(ord_m(a),ord_m(b))=1$，则 $ord_m(ab)=ord_m(a)ord_m(b)$，反过来也成立。

3. 设 $m,n$ 都是大于 $1$ 的整数，$\gcd(a,m)=1$，则
   • 若 $n\mid m$，则 $ord_n(a)\mid ord_m(a)$
   • 若 $\gcd(m,n)=1$，则 $ord_{mn}(a)=GCM\left[ord_m(a),ord_n(a) \right]$

4. 设 $\gcd(a,m)=1$，则对与 $mn$ 互素的任意整数 $a_1,a_2$，存在整数 $a$ 使得 $ord_{mn}=GCM(ord_m(a_1),ord_n(a_2))$。

5. 对与 $m$ 互素的任意整数 $a,b$，存在整数 $c$ 使得 $ord_m(c)=GCM(ord_m(a),ord_m(b))$。

6. 设 $g$ 是模 $p$ 的原根，则 $g$ 或者 $g+p$ 是模 $p^2$ 的原根。

7. 设 $p$ 是奇素数，则对任意 $\alpha$，模 $p^\alpha$ 的原根存在。如果 $g$ 是模 $p^2$ 原根，则对任意 $\alpha$，$g$ 是模 $p^\alpha$ 的原根。