原根

Alumin_Hydro · 2024-08-16 10:51:43 · 个人记录

前言

原神

借鉴于

https://zhuanlan.zhihu.com/p/349128258

https://oi-wiki.org/math/number-theory/primitive-root/

阶

定义

若正整数 a,p 互质并且 p>1，则必然存在一个正整数 n 使得 a^n\equiv 1(\bmod \ p) （欧拉定理）

我们将这个最小的正整数 n 称为 a 模 p 的阶，记作 \delta_p(a)。

性质

没有特别说明的话，全部默认 a,b,n,p 是正整数，且 gcd(a,p)=1,gcd(b,p)=1 且 p>1

1. 对于 i\in[0,\delta_p(a)) 的 i，所有的 a^i\mod p 的结果不相同。

   假设存在 0\leq j<k<\delta_p(a) 满足a_j\equiv a_k(\bmod \ p)，那么 a^{k-j}\equiv 1(\bmod \ p)，这和阶的定义不符。

2. 将 $n$ 分解为 $\delta_p(a)*q+r,0\leq r<\delta_p(a)

   若 r>0，那么 a^r\equiv a^r(a^{\delta_p(a)})^q\equiv a^n\equiv 1(\bmod \ p)

   矛盾

3. \delta_p(a)\mid \varphi(p)

   结合欧拉定理和前两个性质可以得出。

4. \frac{\delta_p(a)}{gcd(\delta_p(a),\delta_p(b))}\mid \delta_p(ab),\frac{\delta_p(b)}{gcd(\delta_p(a),\delta_p(b))}\mid \delta_p(ab),\delta_p(ab)\mid lcm(\delta_p(a),\delta_p(b))

   也可以简写作\frac{lcm(\delta_p(a),\delta_p(b))}{\gcd(\delta_p(a),\delta_p(b))}\mid\delta_p(ab)\mid lcm(\delta_p(a),\delta_p(b))

   首先(ab)^{lcm(\delta_p(a),\delta_p(b))}=a^{lcm(\delta_p(a),\delta_p(b))}b^{lcm(\delta_p(a),\delta_p(b))}=1

   所以\delta_p(ab)\mid lcm(\delta_p(a),\delta_p(b))

   同时，因为((ab)^{\delta_p(ab)})^{\delta_p(b)}=1，所以 a^{\delta_p(ab)\delta_p(b)}=1，所以\delta_p(a)\mid \delta_p(ab)\delta_p(b)，两边除以 \gcd(\delta_p(a),\delta_p(b)) 就得到了 \frac{\delta_p(a)}{gcd(\delta_p(a),\delta_p(b))}\mid \delta_p(ab)\frac{\delta_p(b)}{\gcd(\delta_p(a),\delta_p(b))}，这个分式互素，所以去掉，得到\frac{\delta_p(a)}{gcd(\delta_p(a),\delta_p(b))}\mid \delta_p(ab)

   同理可得另一个。

5. \delta_p(a^k)=\frac{\delta_p(a)}{\operatorname{gcd}(\delta_p(a),k)}

   首先注意到 (a^k)^{\delta_p(a^k)}\equiv 1(\bmod \ p) 就是 a^{k\delta_p(a^k)}\equiv 1(\bmod \ p)，所以\delta_p(a)\mid k\delta_p(a^k)，等同于\frac{\delta_p(a)}{\operatorname{gcd}(k,\delta_p(a))}\mid \delta_p(a^k)。此时 \delta_p(a^k) 的最小值就是 \frac{\delta_p(a)}{\operatorname{gcd}(k,\delta_p(a))}

原根

证明咕咕咕~

定义

设 p\geq3，gcd(g,p)=1，则 g 是 p 的原根的充要条件是：对于 \varphi(p) 的每一个质因数 q，都有 g^{\frac{\varphi(p)}{q}}\not\equiv 1(\bmod \ p) O(\sqrt{\varphi(p)} )

必要性：显然，如果存在更小的肯定不行。

充分性：假设对于 \varphi(p) 的每一个质因数 q，都有 g^{\frac{\varphi(p)}{q}}\not\equiv 1(\bmod \ p) 成立时，g 却不是原根。所以存在 t<\varphi(p)，g^t\equiv 1(\bmod \ p)。由裴蜀定理，存在一组整数 x,y，满足 x*t=y*\varphi(p)+\gcd(t,\varphi(p))。1\equiv g^{x*t}\equiv g^{y*\varphi(p)+\gcd(t,\varphi(p))}\equiv g^{gcd(t,\varphi(p))}(\bmod \ p)

此时必然存在一个质因数 q 使得 gcd(t,\varphi(p))|\frac{\varphi(p)}{q}。

矛盾。

原根个数定理

若一个数 p 有原根，则它的原根个数为 \varphi(\varphi(p))。

当 \gcd(\varphi(p),k)=1 时，\delta_p(g^k)=\varphi(p) ，g^k 是原根。

注意到互质数量为 \varphi(\varphi(p))

原根存在定理

一个数 p 有原根当且仅当 p=2,4,q^a,2q^a,q是奇素数,a\in N^+

有点复杂，不证了。

最小原根的范围估计

素数 p 的最小原根 g=O(p^{0.25+\epsilon})，\epsilon 是一个很小的正数。