阶与原根
引入
根据欧拉定理，我们知道：若 \(a \perp m\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\)。
因此，数列 \(a^1,a^2,a^3,\cdots\) 在模 \(m\) 意义下有一个 \(\varphi(m)\) 的循环节，因为 \(a^{\varphi(m)+1}\equiv a\pmod{m}\)。
然而，我们并不能保证它是最短的循环节。于是我们把这个最短循环节的长度称作为 \(a\) 在模 \(m\) 下的阶，记作 \(\delta_m(a)\)。严格地，定义 \(a\) 在模 \(m\) 下的阶是同余方程 \(a^x\equiv 1\pmod{m}\) 的最小正整数解。
显然，\(\delta_m(a)\) 一定是 \(\varphi(m)\) 的因数。特别地，当 \(\delta_m(a) = \varphi(m)\) 时，我们称 \(a\) 为模 \(m\) 下的一个原根。对于原根 \(a\) 来说，\(a^1,a^2,\cdots,a^{\varphi(m)}\) 在模 \(m\) 下各不相同，他们就是最短的循环节。
阶的性质
性质 \(1\)：若 \(a^n\equiv 1\pmod{m}\)，则 \(\delta_m(a)\mid n\)。
证明：考虑带余除法，设 \(n=\delta_m(a)q+r\)，其中 \(0\le r <\delta_m(a)\)。
性质 \(2\)：设 \(m \in\mathbf{N}\)，\(a,b\in\mathbf{Z}\)，\(\gcd(a,m)=\gcd(b,m)=1\)，则 $$\delta_m(ab)=\delta_m(a)\delta_m(b)$$ 的充分必要条件是 $$\gcd(\delta_m(a),\delta_m(b))=1$$
性质 \(3\)：设 \(k\in\mathbf{N}\)，\(m\in\mathbf{N^*}\)，\(a\in\mathbf{Z}\)，\(\gcd(a,m)=1\)，则 $$\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$