原根学习笔记
阶
对于 \(a \in \mathbb{Z}, m \in \mathbb{N}^+, \gcd(a, m) = 1\)。满足 \(a^n \equiv 1 \pmod m\) 的最小正整数 \(n\) 被称为 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。一般只讨论 \(0 \le a < m\) 的情况。
由欧拉定理可知，阶一定存在。
性质
性质 \(1\)：\(a, a^2, \cdots, a^{\delta_m(a)}\) 在模 \(m\) 意义下互不相同。
证明
考虑反证，若存在 \(1 \le i < j \le \delta_m(a)\) 满足 \(a^i \equiv a^j \pmod m\)，则 \(a^{j - i} \equiv 1 \pmod m\) 且 \(0 < j - i < \delta_m(a)\)，与阶的最小性矛盾。
性质 \(2\)：若 \(a^n \equiv 1 \pmod m\)，则 \(\delta_m(a) \mid n\)。
证明
设 \(n = \delta_m(a)p + q\)，其中 \(0 \le q < \delta_m(a)\)。
若 \(q > 0\)，则
\[a^q \equiv a^q(a^{\delta_m(a)})^p \equiv a^n \equiv 1 \pmod m \]与阶的最小性矛盾，故 \(q = 0\)，故 \(\delta_m(a) \mid n\)。
性质 \(3\)：对于 \(a, b \in \mathbb{Z}, m \in \mathbb{N}^+, \gcd(a, m) = \gcd(b, m) = 1\)，\(\gcd(\delta_m(a), \delta_m(b)) = 1 \Leftrightarrow \delta_m(ab) = \delta_m(a) \delta_m(b)\)。
证明
必要性：
因为 \(a^{\delta_m(a)} \equiv b^{\delta_m(b)} \equiv 1 \pmod m\)。
故 \((ab)^{\operatorname{lcm}(\delta_m(a), \delta_m(b))} \equiv 1 \pmod m\)。
由性质 \(2\)得 \(\delta_m(ab) \mid \operatorname{lcm}(\delta_m(a), \delta_m(b))\)。
因为 \(\delta_m(ab) = \delta_m(a) \delta_m(b)\)，故 \(\delta_m(a) \delta_m(b) \mid \operatorname{lcm}(\delta_m(a), \delta_m(b))\)。
故 \(\gcd(delta_m(a), \delta_m(b)) = 1\)。
充分性：
\[1 \equiv (ab)^{\delta_m(ab)} \equiv \left((ab)^{\delta_m(ab)}\right)^{\delta_m(b)} \equiv (ab)^{\delta_m(ab) \delta_m(b)} \equiv a^{\delta_m(ab) \delta_m(b)} b^{\delta_m(ab) \delta_m(b)} \equiv a^{\delta_m(ab) \delta_m(b)} \pmod m \]由性质 \(1\) 得 \(\delta_m(a) \mid \delta_m(ab)\delta_m(b)\)。
又因为 \(\gcd(\delta_m(a), \delta_m(b)) = 1\)，故 \(\delta_m(a) \mid \delta_m(ab)\)。
同理，\(\delta_m(b) \mid \delta_m(ab)\)。
所以 \(\delta_m(a) \delta_m(b) \mid \delta_m(ab)\)。
又有 \(\delta_m(ab) \mid \operatorname{lcm}(\delta_m(a), \delta_m(b))\) 且 \(\gcd(\delta_m(a), \delta_m(b)) = 1\)，故 \(\delta_m(a) \mid \delta_m(a) \delta_m(b)\)。
故 \(\delta_m(ab) = \delta_m(a) \delta_m(b)\)。
性质 \(4\)：对于任意 \(k \in \mathbb{N}\)，有 \(\delta_m(a^k) = \dfrac{\delta_m(a)}{\gcd(\delta_m(a), k)}\)。
证明
由于
\[a^{k\delta_m(a^k)} = (a^k)^{\delta_m(a^k)} \equiv 1 \pmod m \]故 \(\delta_m(a) \mid k \delta_m(a^k)\)。故 \(\dfrac{\delta_m(a)}{\gcd(\delta_m(a), k)} \mid \delta_m(a^k)\)。
另一方面，设 \(u = \dfrac{1}{\gcd(\delta_m(a), k)}\)，则
\[(a^k)^\dfrac{\delta_m(a)}{u} = a^{\dfrac{k \delta_m(a)}{u}} = (a^{\delta_m(a)})^{\dfrac{k}{u}} \equiv 1 \pmod m \]故 \(\delta_m(a^k) \mid \dfrac{\delta_m(a)}{\gcd(\delta_m(a), k)}\)。
故 \(\delta_m(a^k) = \dfrac{\delta_m(a)}{\gcd(\delta_m(a), k)}\)。
原根
对于 \(m \in \mathbb{N}^+\)，若 \(a \in \mathbb{Z}, \gcd(a, m) = 1, \delta_m(a) = \varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。一般只讨论 \(0 \le a < m\) 的情况。
原根判定定理
对于 \(m \ge 3, \gcd(a, m) = 1\)，\(a\) 是模 \(m\) 的原根的充要条件是 \(\forall p \in \mathbb{P}, p \mid \varphi(m)\)，有 \(a^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m\)。
证明
必要性显然。
考虑证明充分性，假设存在一个 \(a\) 满足 \(\forall p \in \mathbb{P}, p \mid \varphi(m)\)，有 \(a^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m\) 但不是模 \(m\) 的原根，则 \(\delta_m(a) < \varphi(m)\) 且 \(\delta_m \mid \varphi(m)\)。则必然存在一个 \(p \in \mathbb{P}, p \mid \varphi(m)\) 满足 \(\delta_m(a) \mid \dfrac{\varphi(m)}{p}\)，则 \(a^{\frac{\varphi(m)}{p}} \equiv 1 \pmod m\)。与假设矛盾。
原根个数
若 \(m\) 存在原根，则它的原根个数为 \(\varphi(\varphi(m))\)。
证明
若 \(m\) 有原根 \(g\)，则
\[\delta_m(g^k) = \dfrac{\delta_m(g)}{\gcd(\delta_m(g), k)} = \dfrac{\varphi(m)}{\gcd(\varphi(m), k)} \]所以若 \(\gcd(k, \varphi(m)) = 1\)，则 \(\delta_m(g^k) = \varphi(m)\)，故 \(g^k\) 也是 \(m\) 的原根。
故 \(m\) 的原根的个数为满足 \(\gcd(\varphi(m), k) = 1\) 的 \(k\) 的个数，即 \(\varphi(\varphi(m))\)。
原根存在定理
一个数 \(m\) 存在原根当且仅当 \(m \in \{2, 4, p^k, 2p^k\}\)，其中 \(p \in \mathbb{P}, k \in \mathbb{N}^+\)。
证明过于答辩，略。
最小原根的数量级
若 \(m\) 有原根，其最小原根不多于 \(m^{0.25}\) 级别。
证明略。
由于这个定理，暴力求一个数的最小原根的复杂度是可以接受的。
标签：ab,gcd,原根,笔记,学习,varphi,delta,equiv From： https://www.cnblogs.com/mk-oi/p/Protoroot.html