阶与原根
贡献者： int256
引理 1
对于命题 $P(n)$ 而言，若对于每个 $a$, $b$ 都有 $P(a)$ 与 $P(b)$ 蕴含 $P(a+b)$ 且至少在 $b \le a$ 时蕴含 $P(a-b)$，而 $r$ 是使 $P$ 成立的最小正正数，则：
- 对于各个自然数 $k = 1, 2, \dots$，$P(kr)$ 也为真。
- 任何使得 $P(m)$ 成立的非负整数 $m$ 都是 $r$ 的倍数。
证明：对于第一点是显然的，由于 $P(r)$ 与 $P(r)$ 都为真，故 $P(r+r)$ 为真......
现在考虑第二点。根据 $r$ 的定义，$0 < r \le m$，记 $m = qr + s$，从而 $s = m - qr$，其中 $0 \le s < r$ 而 $q \ge 1$。根据第一点，$P(r) \rightarrow P(kr)$，而 $P(a)$ 与 $P(b)$ 蕴含 $P(a \pm b)$，故 $P(m)$ 与 $P(qr)$ 可以推导出 $P(s)$。而由于 $r$ 的定义，$s$ 必定为 $0$。故 $q = kr$。证毕！
定义 1 阶
记 $d$ 是使得
\begin{equation}
a^x \equiv 1 \pmod m ~~
\end{equation}
的最小正整 $x$，则称 $d$ 为 $a$ 模 $m$ 意义下的
阶（order）。
定义 2 原根
特别的，若 $d$ 是 $a$ 模 $m$ 的阶，且 $d = \varphi(m)$，则称 $d$ 是 $a$ 模 $m$ 的原根（primitive root）。
考虑阶的条件，记
\begin{equation}
P(x) : a^x \equiv 1 \pmod m ~,
\end{equation}
这会使得 $P(x)$ 与 $P(y)$ 显然蕴含 $P(x+y)$，而在 $y \le x$ 时，
\begin{equation}
a^{x-y} \equiv b \pmod m ~,
\end{equation}
则
\begin{equation}
a^x \equiv b a^y \pmod m ~,
\end{equation}
故必定 $b=1$ 而 $P(x)$ 与 $P(y)$ 在 $y \le x$ 时蕴含 $P(x-y)$。这就使得符合
引理 1 的条件，这就指出 $d | \varphi(m)$。
阶与原根可以理解为数论上的某种本原单位根。