阶：

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

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

性质：

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

若 \(a^n \equiv 1 \pmod m\)，则 \(\delta_m(a)\mid n.\)

若 \(a^p\equiv a^q\pmod m\)，则有 \(p\equiv q\pmod{\delta_m(a)}.\)

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

\(\delta_m(ab)=\delta_m(a)\delta_m(b)\) 的充分必要条件是 \(\left(\delta_m(a), \delta_m(b)\right)=1\)

设 \(k \in \mathbf{N}\)，\(m\in \mathbf{N}^{*}\)，\(a\in\mathbf{Z}\)，\((a,m)=1\)，则 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)}\)

原根：

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

即 \(g\) 满足 \(\delta_m(g) = \left| \mathbf{Z}_m^* \right| = \varphi(m)\). 当 \(m\) 是质数时，我们有 \(g^i \bmod m,\,0 \lt i \lt m\) 的结果互不相同。

1 原根判定定理:

设 \(m \geqslant 3, (g,m)=1\)，则 \(g\) 是模 \(m\) 的原根的充要条件是，对于 \(\varphi(m)\) 的每个素因数 \(p\)，都有 \(g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m.\)

2 原根存在定理:

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