【笔记】原根

标签：ab 原根 pmod mid 笔记 delta equiv

阶

定义

阶：满足同余式 \(a^n \equiv 1 \pmod m\) 的最小正整数 \(n\) 存在，称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。

性质

1. \(a,a^2,\ldots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余；

2. \(a^n \equiv 1 \pmod m \iff \delta_m(a) \mid n\)；

• 推论：\(a^p \equiv a^q \pmod m \iff p \equiv q \pmod {\delta_m(a)}\)

3. 设 \(m \in \mathbb{N}^*\)，\(a,b \in \mathbb{Z}\)，\(\gcd(a,m) = \gcd(b,m) = 1\)，则：

\[\delta_m(ab) = \delta_m(a)\delta_m(b) \iff \gcd(\delta_m(a),\delta_m(b)) = 1 \]

证明：

1. 充分性：

\[\begin{aligned}&\because (ab)^{\delta_m(ab)} \equiv 1 \pmod m\\&\therefore (ab)^{\delta_m(ab)\delta_m(b)} \equiv 1 \pmod m\\&\therefore a^{\delta_m(ab)\delta_m(b)} \equiv 1 \pmod m\\&\therefore \delta_m(a) \mid \delta_m(ab)\delta_m(b)\\[1ex]&\because \gcd(\delta_m(a),\delta_m(b)) = 1\\&\therefore \delta_m(a) \mid \delta_m(ab)\end{aligned} \]

对称地，可得：

\[\delta_m(b) \mid \delta_m(ab) \]

于是：

\[\delta_m(a)\delta_m(b) \mid \delta_m(ab) \]

而又有：

\[\begin{aligned}&\because\left(a^{\delta_m(a)}\right)^{\delta_m(b)}\left(b^{\delta_m(b)}\right)^{\delta_m(a)} \equiv 1 \pmod m\\&\therefore (ab)^{\delta_m(a)\delta_m(b)} \equiv 1 \pmod m\end{aligned} \]

易得：

\[\delta_m(ab) \mid \delta_m(a)\delta_m(b) \]

综上：

\[\delta_m(a)\delta_m(b) = \delta_m(ab) \]

2. 必要性

\[\begin{aligned}&\because a^{\delta_m(a)}\equiv 1 \pmod m \And b^{\delta_m(b)} \equiv 1 \pmod m\\&\therefore (ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))} \equiv 1 \pmod m\\&\therefore\delta_m(ab) \mid \operatorname{lcm}(\delta_m(a),\delta_m(b))\\&\quad \implies \delta_m(a)\delta_m(b) \mid\operatorname{lcm}(\delta_m(a),\delta_m(b))\\&\therefore \gcd(\delta_m(a),\delta_m(b)) = 1\end{aligned} \]

4. 设 \(k \in \mathbb{N}\)，\(m \in \mathbb{N}^*\)，\(a \in \mathbb{Z}\)，\(\gcd(a,m) = 1\)，则：

\[\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]

证明：

\(\because \delta_m(a) \mid k\cdot \delta_m(a^k)\)

鉴于阶的最小性，所以 \(\delta_m(a^k)\) 的取值为 \(\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)。

原根

定义

设 \(m \in \mathbb{N}^*\)，\(a \in \mathbb{Z}\)。若 \(\gcd(a,m) = 1 \land \delta_m(a) = \varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。

原根判定定理

设 \(a,m \in \mathbb{N}^*\) 且 \(\gcd(a,m) = 1\)，则：

\[a\ \text{是模}\ m\ \text{意义下的原根}\ \iff \forall p \mid \varphi(m)\,(p \in prime),m \not\mid a^{\frac{\varphi(m)}{q}-1} \]

原根个数

\[\text{若}\ m \ \text{有原根，则其原根个数为}\ \varphi(\varphi(m)) \]

原根存在定理

\[m\ \text{有原根}\ \iff n = \begin{cases}1\\2\\4\\p^k\\2p^k\end{cases},(p\ \text{为奇素数}\ ,k \ge 1) \]

最小原根的数量级

若一个数 \(m\) 有原根，则它的最小原根不大于 \(m^{0.25}\)。

标签：ab,原根,pmod,mid,笔记,delta,equiv
From： https://www.cnblogs.com/bikuhiku/p/primitive_root.html