$\S 5.1 $ 整数的次数

定义

设 $m>0,\ \gcd(m,a)=1,\ l$ 是使 $a^l\equiv 1 \pmod{m}$ 成立的最小正整数. 则 $l$ 叫做 $a$ 对模数 $m$ 的次数（也叫阶）. 记作 $\operatorname{ord}_m(a)=l$.

注：当 $\gcd(m,a) \neq 1$ 时，$a^k \equiv 1 \pmod{m}$ 永远不成立，此时次数无定义。

性质 1

设 $\operatorname{ord}_m(a)=l$，则

\[ a^k \equiv 1 \pmod{m} \iff l \mid k \]

证明：$(\Leftarrow)$ 若 $l \mid k$，设 $k = ql$，则 $a^k = (a^l)^q \equiv 1^q = 1 \pmod{m}$.

$(\Rightarrow)$ 若 $a^k \equiv 1 \pmod{m}$，由带余除法 $k = ql + r,\ 0 \le r < l$，则

\[ 1 \equiv a^k = a^{ql+r} = (a^l)^q \cdot a^r \equiv a^r \pmod{m} \]

而 $l$ 是使同余式成立的最小正整数，故 $r = 0$，即 $l \mid k$. $\quad \square$

性质 2

\[ \operatorname{ord}_m(a) \mid \varphi(m) \]

证明：由欧拉定理，$a^{\varphi(m)} \equiv 1 \pmod{m}$，再由性质 1 即得. $\quad \square$

性质 3

设 $\operatorname{ord}_m(a)=l$，则

\[ a^i \equiv a^j \pmod{m} \iff i \equiv j \pmod{l} \]

证明：不妨设 $i \ge j$，则 $a^i \equiv a^j \pmod{m} \iff a^{i-j} \equiv 1 \pmod{m}$（因为 $\gcd(a,m)=1$，$a^j$ 可约去），由性质 1 即得. $\quad \square$

性质 4

设 $\operatorname{ord}_m(a)=l$，则对任意正整数 $k$，

\[ \operatorname{ord}_m(a^k) = \frac{l}{\gcd(l, k)} \]

证明：令 $d = \gcd(l,k),\ l = l_1 d,\ k = k_1 d$，其中 $\gcd(l_1, k_1) = 1$.

设 $\operatorname{ord}_m(a^k) = t$. 由 $(a^k)^{l_1} = (a^l)^{k_1} \equiv 1 \pmod{m}$，知 $t \mid l_1$.

又 $(a^k)^t = a^{kt} \equiv 1 \pmod{m}$，由性质 1 有 $l \mid kt$，即 $l_1 d \mid k_1 d t$，故 $l_1 \mid k_1 t$.

而 $\gcd(l_1, k_1) = 1$，所以 $l_1 \mid t$.

综上 $t = l_1 = \dfrac{l}{\gcd(l,k)}$. $\quad \square$

推论：$a^k$ 的次数等于 $l$ 当且仅当 $\gcd(l, k) = 1$.

性质 5

设 $\operatorname{ord}_m(a)=l_1,\ \operatorname{ord}_m(b)=l_2$，且 $\gcd(l_1, l_2) = 1$，则

\[ \operatorname{ord}_m(ab) = l_1 l_2 \]

证明：设 $\operatorname{ord}_m(ab) = t$.

一方面，$(ab)^{l_1 l_2} = (a^{l_1})^{l_2} \cdot (b^{l_2})^{l_1} \equiv 1 \pmod{m}$，故 $t \mid l_1 l_2$.

另一方面，由 $(ab)^t \equiv 1 \pmod{m}$，有

\[ 1 \equiv (ab)^{t l_2} = a^{t l_2} \cdot b^{t l_2} \equiv a^{t l_2} \pmod{m} \]

故 $l_1 \mid t l_2$，又 $\gcd(l_1, l_2) = 1$，故 $l_1 \mid t$. 同理 $l_2 \mid t$.

由 $\gcd(l_1, l_2) = 1$，得 $l_1 l_2 \mid t$.

综上 $t = l_1 l_2$. $\quad \square$

性质 6

设 $p$ 是一个素数，若存在 $a$ 满足 $\operatorname{ord}_p(a) = l$，则恰有 $\varphi(l)$ 个对模数 $p$ 两两不同余的整数，它们对模数 $p$ 的次数都是 $l$.

证明：考虑 $l$ 个数

\[ a^0,\ a^1,\ a^2,\ \ldots,\ a^{l-1} \]

它们两两不同余（由性质 3，$a^i \equiv a^j \iff l \mid i-j$，而 $0<|i-j|<l$），且对每个 $k$ 有 $(a^k)^l = (a^l)^k \equiv 1 \pmod{p}$，即它们都是同余式

\[ \begin{equation} x^l \equiv 1 \pmod{p} \end{equation} \]

的解.

而 $(1)$ 是模素数 $p$ 的 $l$ 次同余式，由多项式同余理论，它最多有 $l$ 个解. 故这 $l$ 个数就是 $(1)$ 的全部解.

由性质 4，$\operatorname{ord}_p(a^k) = \dfrac{l}{\gcd(l, k)}$，故 $a^k$ 的次数等于 $l$ 当且仅当 $\gcd(l, k) = 1$.

而在 $0, 1, \ldots, l-1$ 中与 $l$ 互素的 $k$ 恰有 $\varphi(l)$ 个. $\quad \square$

性质 7

设 $l \mid p-1$，则次数为 $l$ 的模 $p$ 互不同余的整数个数为 $\varphi(l)$ 个.

证明：由性质 2，对任意 $\gcd(a, p) = 1$ 有 $\operatorname{ord}_p(a) \mid p-1$.

我们在第五章后面将证明模素数必有原根（即存在 $g$ 使 $\operatorname{ord}_p(g) = p-1$）. 取原根 $g$，则 $$ a = g^{\frac{p-1}{l}} $$

的次数为 $\operatorname{ord}_p(a) = \dfrac{p-1}{\gcd\left(\frac{p-1}{l},\ p-1\right)} = \dfrac{p-1}{\frac{p-1}{l}} = l$.

因此对任意 $l \mid p-1$，次数为 $l$ 的元素必然存在. 再由性质 6，其个数恰为 $\varphi(l)$. $\quad \square$

注：当 $l = p-1$ 时，$\varphi(p-1)$ 就是模 $p$ 原根的个数.