阶与原根
贡献者： 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)$。
阶与原根可以理解为数论上的某种本原单位根。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。