原根

Tangninghaha · 2025-01-07 21:29:12 · 算法·理论

同余类与剩余系

定义 1.1：同余

若 a\equiv b\pmod{m} 时，称 a 和 b 关于 m 同余。

定义 1.2：同余类

在模 m 意义下，所有与 a 同余的数在同一个同余类中。记作 \overline{a_m}。

一个同余类中任意元素可以成为该同余类的代表元。假设一个同余类代表元为 a，则该同余类可以表示为 \{a+km\},k\in \mathbb{Z}。

定义 1.3：完全剩余系

对 m 取模的同余类有 m 个，分别是 \overline{0_m},\overline{1_m},\cdots\overline{{m-1}_{m}}。在每一个同余类中选取一个代表元得到的集合称为 m 的完全剩余系。

定义 1.4：简化剩余系

在完全剩余系中，只保留与 m 互素的数，得到的即为简化剩余系。

欧拉定理

定义 2.1：欧拉函数

记在 [1,m] 中与 m 互质的数的个数为 \varphi(m)，这个函数被称为欧拉函数。

命题 2.1：欧拉定理

若 \gcd(a,n)=1，则 a^{\varphi(n)}\equiv 1\pmod{n}

命题 2.1 的证明：

设 n 的简化剩余系为 \{a_1,a_2,\cdots,a_{\varphi(n)}\}。若有 \gcd(a,n)=1，易证 \{aa_1,aa_2,\cdots,aa_{\varphi(n)}\} 仍然是 n 的一个简化剩余系。

故有 a_1a_2\cdots a_{\varphi(n)}\equiv aa_1aa_2\cdots aa_{\varphi(n)}\equiv a^{\varphi(n)}a_1a_2\cdots a_{\varphi(n)}\pmod{n}。

即 a^{\varphi(n)}\equiv 1\pmod{n}。

命题 2.2：费马小定理

对于质数 p，有 a^{p-1}\equiv 1\pmod{n}。

命题 2.2 的证明：

容易知道 \varphi(p)=p-1，由命题 2.1 容易得证。

阶

定义 3.1

若 \gcd(a,m)=1，则最小的 r 满足 a^{r}\equiv 1\pmod{m} 被称为 a 模 m 的阶，记作 \delta_m{(a)}。

由欧拉定理得到，当 \gcd(a,m)=1 时必然有 a^{\varphi(m)}\equiv 1\pmod{m}，即阶一定存在，且 \delta_m(a)\le \varphi(m)。

命题 3.1

充分性显然，反证其必要性：

假设存在 \delta_m(a)\nmid d，设 d=k\delta_m(a)+r，其中 r<\delta_m(a)。

则有 a^{k\delta_m(a)+r}\equiv 1\pmod{m}，则有 a^{r}\equiv 1\pmod{m}，根据阶的定义，r 应该是 a 模 m 的阶，与假设矛盾。

命题 3.2：幂的阶

若 k 是非负整数，则有

\delta_m(a^{k})=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}

有一个很厉害的证明：

引理一：显然，若 a\mid b 且 b\mid a，则 a=b。

引理二：若 a\mid kb，则 \frac{a}{\gcd(a,k)}\mid b。

为了证明上面这一点，观察到这个命题与指数有很强的联系，所以在指数上考虑问题。并充分利用命题 3.1 和引理二来建立引理一中的等式：

故根据命题 3.1 有：

根据引理二有：

另一方面，我们还希望得到

注意到 a^{\delta_m(a)}\equiv 1\pmod{m}，则：

这正是我们想要的。

综上，由引理一，证毕。

原根

定义 4.1：原根

若 \gcd(a,m)=1（这是阶定义的一部分），且 \delta_m(a)=\varphi(m)，则称 a 是模 m 的一个原根。

命题 4.1：原根个数

引理三：假设 g 是模 m 的一个原根，则集合 \{g^{k},0\le k< \varphi(m)\} 是 m 的一个简化剩余系。

证明引理三，只要考虑 g 的定义，由于 g 的阶为 \varphi(m)，则 g^{k} 在模 m 意义下必然互不相同（否则可以推出 g 的阶小于 \varphi(m)）。

由引理三，只要知道 g^{k} 中有多少个是原根即可。

由命题 3.2，可以知道 \delta_{m}(g^{k})=\frac{\delta_m(g)}{\gcd(\delta_m(g),k)}。如果 g^{k} 是原根，那么 \delta_m(g^{k})=\delta_m(g)，即 \gcd(\delta_m(g),k)=1。满足条件的 k 有 \varphi(\delta_m(g))=\varphi(\varphi(m)) 个。

命题 4.2：原根判定定理

若 \varphi(m) 的本质不同质因子为 p_1,p_2,\cdots,p_s，则若 g 是模 m 的原根的充要条件是

\forall 1\le i\le s,g^{\frac{\varphi(m)}{p_i}}\not\equiv 1\pmod{m}

必要性容易说明：反证：若存在等于 1，与阶的最小性矛盾。

充分性也不难说明：反证：若存在 k<\varphi(m) 且 g^{k}\equiv 1\pmod m，则根据命题 3.1 有 k\mid \varphi(m)。由于 k\not=\varphi(m)，则必然存在一个 p_i（例如 \frac{\varphi(m)}{k} 的最小质因子），满足 k\mid \frac{\varphi(m)}{p_i}，此时g^\frac{\varphi(m)}{p_i}\equiv 1\pmod{m}，与假设矛盾。

从另一个角度，由于 \delta_m(g)\mid \varphi(m)，则只要 \varphi(m) 非自身因数都不是 g 的阶即可。但并不需要考虑所有因数，只需要考虑除去某一个质因子以后的因数即可，因为这隐含了其它因数。

命题 4.3：原根存在定理

一个数存在原根，当且仅当，其形如 2，4，p^{k}，2p^{k}，其中 p 是奇素数，k\in \N^{*}。

证明还不会。

求原根

P6091 【模板】原根 - 洛谷

直接使用 O(n\log^2 n) 的方法计算可以计算原根。

分成下面几步：

1. 计算 \varphi(n) 的值。
2. 对 \varphi(n) 分解质因子。
3. 求出最小原根 g。
4. 枚举 i=1\to \varphi(n)，如果 (\varphi(g),i)=1，那么 g^i 就是一个原根。
5. 排序输出即可。

分析一下复杂度，第一步是 O(\sqrt{n}) 的，第二步是 O(\sqrt{\varphi(n)}) 的。

第三步要先枚举 1 到 n，逐个判断，单次判断是 O(\log^2 n) 的，一个是快速幂的复杂度，一个是 \varphi(n) 的质因子个数。

第四步是 O(\varphi(n)\log n) 的。最后一步是 O(\varphi(n)\log \varphi(n)) 的。

这样瓶颈在第三步，至多需要枚举 n 个位置，复杂度是 O(n\log^{2}n) 的。

关于最小原根，王元证明一个素数的最小原根 p 是 O(p^{0.25}) 级别的，而 Fridlande 和 Salié 证明了素数 p 的最小原根是 \Omega(\log p) 的。这使得至少在求素数的原根时，复杂度在一个可接受的范围内。但是对于非素数的最小原根，至少我并不确切地知道其范围。