阶与原根学习笔记

什么是阶

若 $(a,m)=1$(a,m)=1，则使 $a^l\equiv 1\left(modm\right)$al≡1 (mod m) 的最小 $l$l，称之为 $a$a 关于模 $m$m 的阶，记为 $or{d}_{m}a$ordm​a
举个例子：
比如要求 $2$2 模 $7$7 的阶，可以一一列举 $2$2 的幂次：
$2^1\equiv 2\left(mod7\right)$21≡2 (mod 7)
$2^2\equiv 4\left(mod7\right)$22≡4 (mod 7)
$2^3\equiv 1\left(mod7\right)$23≡1 (mod 7)
$2^4\equiv 2\left(mod7\right)$24≡2 (mod 7)
$2^5\equiv 4\left(mod7\right)$25≡4 (mod 7)
$2^6\equiv 1\left(mod7\right)$26≡1 (mod 7)
于是可以看出， $2$2 模 $7$7 的阶为 $3$3。

阶的性质

1. 根据欧拉定理，我们有 $a^{\phi \left(m\right)}\equiv 1\left(modm\right)$aφ(m)≡1 (mod m)。
   于是 $or{d}_{m}a\mid \phi \left(m\right)$ordm​a∣φ(m)。
2. 当 $a^x\equiv 1\left(modm\right)$ax≡1 (mod m) 时， $or{d}_{m}a\mid x$ordm​a∣x
3. 阶相当于最小循环节，即 $a^x\equiv a^{x+or{d}_{m}a}\left(modm\right)$ax≡ax+ordm​a (mod m)。因此 $a^1,a^2,....,a^{or{d}_{m}a}$a1,a2,....,aordm​a 构成模 $m$m 意义下的一个既约剩余系。从上述例子也可以看出，如 $2^1\equiv 2^4\left(mod7\right)$21≡24 (mod 7)。
4. $or{d}_m{a}^t=\frac{or{d}_{m}a}{\gcd (or{d}_{m}a,t)}$ordm​at=gcd(ordm​a,t)ordm​a​，证明如下：
   当 $a^{t\ast l}\equiv 1\left(modm\right)$at∗l≡1 (mod m)时， $or{d}_{m}a\mid t\ast l,t\mid t\ast l$ordm​a∣t∗l,t∣t∗l，因此 $l$l 最小时， $t\ast l$t∗l 应为 $lcm(t,or{d}_{m}a)$lcm(t,ordm​a)，可以推得 $l=\frac{or{d}_{m}a}{\gcd (or{d}_{m}a,t)}$l=gcd(ordm​a,t)ordm​a​

原根

当 $or{d}_{m}a=\phi \left(m\right)$ordm​a=φ(m) 时，称 $a$a 为关于 $m$m 的原根。
也就是说，使得 $a^x\equiv 1\left(modm\right)$ax≡1 (mod m) 成立的最小 $x$x 为 $\phi \left(m\right)$φ(m)。
举个例子：
$7$7 的原根是 $3$3，因为：
$3^1\equiv 3\left(mod7\right)$31≡3 (mod 7)
$3^2\equiv 2\left(mod7\right)$32≡2 (mod 7)
$3^3\equiv 6\left(mod7\right)$33≡6 (mod 7)
$3^4\equiv 4\left(mod7\right)$34≡4 (mod 7)
$3^5\equiv 5\left(mod7\right)$35≡5 (mod 7)
$3^6\equiv 1\left(mod7\right)$36≡1 (mod 7)
于是只有 $3^{\phi \left(7\right)}\equiv 1\left(mod7\right)$3φ(7)≡1 (mod 7)。
再举一个非素数的例子，比如 $5$5 是 $18$18 的一个原根。 $\phi \left(18\right)=6$φ(18)=6
$5^1\equiv 5\left(mod18\right)$51≡5 (mod 18)
$5^2\equiv 7\left(mod18\right)$52≡7 (mod 18)
$5^3\equiv 17\left(mod18\right)$53≡17 (mod 18)
$5^4\equiv 13\left(mod18\right)$54≡13 (mod 18)
$5^5\equiv 11\left(mod18\right)$55≡11 (mod 18)
$5^6\equiv 1\left(mod18\right)$56≡1 (mod 18)
于是最小的 $x$x 使得 $5^x\equiv 1\left(mod18\right)$5x≡1 (mod 18) 是 $\phi \left(18\right)$φ(18)，也就是 $6$6。

原根的性质

1. 当 $g$g 为原根时， $g^1,g^2,....,g^{\phi \left(m\right)}$g1,g2,....,gφ(m) 构成模 $m$m 意义下的既约剩余系。
   从上面 $5$5 是 $18$18 的原根可以看到， $5^1$51 到 $5^6$56 模 $18$18 之后恰好是 $6$6 个和 $18$18 互质的数。
   具体证明也不难，因为 $g$g 和 $m$m 互质，因此 $g^x$gx 和 $m$m 互质，总共有 $\phi \left(m\right)$φ(m) 个 $x$x，于是生成了 $\phi \left(m\right)$φ(m) 个与 $m$m 互质的数，也就是 $m$m 的既约剩余系。
2. 如果 $m$m 有原根，那么 $m$m 总共有 $\phi \left(\phi \right(m\left)\right)$φ(φ(m)) 个原根。
   证明一下：
   设 $g$g 为 $m$m 的一个原根。那么所有原根肯定存在于 $g^1,g^2,...,g^{\phi \left(m\right)}$g1,g2,...,gφ(m) 中，因为原根肯定与 $m$m 互质。那么我们考虑 $g$g 的幂次。
   当 $or{d}_m{g}^t=\phi \left(m\right)$ordm​gt=φ(m) 时， $g^t$gt 为 $m$m 的原根，我们来看看这样的 $t$t 有多少个。由阶的性质 $4$4， $or{d}_m{g}^t=\frac{\phi \left(m\right)}{\gcd \left(\phi \right(m),t)}=\phi \left(m\right)$ordm​gt=gcd(φ(m),t)φ(m)​=φ(m) 时， $\gcd \left(\phi \right(m),t)=1$gcd(φ(m),t)=1，也就是说，这样的 $t$t 有 $\phi \left(\phi \right(m\left)\right)$φ(φ(m)) 个。
3. 从上面的证明我们可以看到，若 $g$g 为 $m$m 的一个原根，则所有原根集合为 $\{g^s\mid 1\le s\le \phi (m),(s,\phi \left(m\right)=1\left)\right\}${gs∣1≤s≤φ(m),(s,φ(m)=1)}

原根的作用

原根的最大意义在于，它可以映射 $m$m 的既约剩余系，而且每个元素一一对应。
比如我们在求 $x^a\equiv b\left(modm\right)$xa≡b (mod m) （ $m$m 是质数）时，我们可以设 $g^t\equiv x\left(modm\right)$gt≡x (mod m)，其中 $g$g 为 $m$m 的原根，不难证明这样的 $t$t 一定存在。且一个 $t$t 与一个 $x$x 一一对应。
那么即是求 $(g^t{)}^a\equiv (g^a{)}^t\equiv b\left(modm\right)$(gt)a≡(ga)t≡b (mod m) 的 $t$t。因为 $g^a$ga 已知，所以用 $BSGS$BSGS 求 $t$t 即可。
原根还在 $NTT$NTT 中有着重要的作用。
于是学习原根其实是在为学 NTT 做铺垫。

原根存在的条件

当 $m=2,4,p^k,2\ast p^k$m=2,4,pk,2∗pk （ $p$p 为奇素数）时， $m$m 的原根存在。其余情况不存在原根。
证明的话，我不会证。。

如何求原根

因为原根密度很大，大约是 $n^{0.25}$n0.25，所以可以考虑暴力枚举找到一个原根。
当枚举到 $a$a 时，如何快速判断 $a$a 是不是原根呢？注意 $a,m$a,m 要互质。
$a$a 不是原根的条件是，存在 l<φ(m)，使得 $a^l\equiv 1\left(modm\right)$al≡1 (mod m)。
设 $\phi \left(m\right)=\prod p_i^{k_i}$φ(m)=∏piki​​
由于 $l$l 是 $\phi \left(m\right)$φ(m) 的约数，所以我们预处理 $\phi \left(m\right)$φ(m) 的素因子，然后枚举素因子 $p_i$pi​，判断是否 $a^{\frac{\phi \left(m\right)}{p_i}}\equiv 1\left(modm\right)$api​φ(m)​≡1 (mod m) 即可。
单次判断复杂度是 $O\left(lo{g}^{2}n\right)$O(log2n) 的。
这里有一道模板题

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
	   static uint64_t splitmix64(uint64_t x) {
	   	x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
LL z = 1;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
int phi(int x){
	int ret = x;
	for(int i = 2; i <= x / i; i++){
		if(x % i == 0){
			ret = ret / i * (i - 1);
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) ret = ret / x * (x - 1);
	return ret;
}
vector<int> d;
void get(int x){
	for(int i = 2; i <= x / i; i++){
		if(x % i == 0){
			d.push_back(i);
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) d.push_back(x);
}
int main(){
	int i, j, flag, n, p, m;
	p = read(); m = phi(p);
	get(m);
	for(i = 2; i <= p; i++){
		flag = 0;
		for(auto x: d){
			if(ksm(i, m / x, p) == 1){
				flag = 1;
				break;
			}
		}
		if(!flag){
			printf("%d", i);
			return 0;
		}
	}
	return 0;
}