原根

階

定義

由歐拉定理，對(duì)于 \(a\in\mathbf Z\)，\(m\in\mathbf N^*\)，若 \(a,m\) 互質(zhì)，則 \(a^{\varphi(m)}\equiv1\pmod m\)。

因此滿足同余式 \(a^n\equiv1\pmod m\) 的最小整數(shù) \(n\) 存在，這個(gè) \(n\) 就被稱為 \(a\) 模 \(m\) 的階，記作 \(\delta_m(a)\)。

性質(zhì)

1. \(a,a^2,\dots,a^{\delta_m(a)}\) 模 \(m\) 兩兩不同余。

2. 若 \(a^n\equiv1\pmod m\)，則 \(\delta_m(a)\mid n\)。可推得：若 \(a^p\equiv a^q\pmod m\)，則 \(p\equiv q\pmod{\delta_m(a)}\)。

3. 對(duì)于 \(a,b\in\mathbf Z\)，\(m\in\mathbf N^*\)，若 \(a,b\) 都和 \(m\) 互質(zhì)，則有

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

4. 對(duì)于 \(a\in\mathbf Z\)，\(m\in\mathbf N^*\)，\(k\in\mathbf N\)，若 \(a,m\) 互質(zhì)，則

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

原根

定義

設(shè) \(g\in\mathbf Z\)，\(m\in\mathbf N^*\)，若 \(g,m\) 互質(zhì)，且 \(\delta_m(g)=\varphi(m)\)，則稱 \(g\) 為模 \(m\) 的原根。

原根判定定理

沿用上述條件，\(g\) 為模 \(m\) 的原根的充要條件是：對(duì)于 \(\varphi(m)\) 的任意一個(gè)質(zhì)因子 \(p\)，都滿足 \(g^{\frac{\varphi(m)}p}\not\equiv1\pmod m\)。

原根個(gè)數(shù)

若一個(gè)數(shù) \(m\) 有原根，則它的原根個(gè)數(shù)為 \(\varphi(\varphi(m))\) 個(gè)。

若 \(g\) 是模 \(m\) 的最小原根，\(k\) 和 \(\varphi(m)\) 互質(zhì)，則 \(g^k\) 也是模 \(m\) 的原根。

原根存在定理

若一個(gè)數(shù) \(m\) 有原根，當(dāng)且僅當(dāng) \(m=2,4,p^k,2p^k\)，其中 \(p\) 是奇質(zhì)數(shù)。

求原根

先判斷該數(shù)字是否有原根，如果有就暴力枚舉最小原根 \(g\)，根據(jù)原根判定定理判斷其是否合法。若合法，就用原根個(gè)數(shù)定理中的條件去找出剩下的 \(g^k\) 這些原根即可。

P6091 【模板】原根

#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN=1e6+5;
int T,n,d;
vector<int>pri,v,ans;
int phi[MAXN];
bool isp[MAXN];
int rt[MAXN];

void init(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!isp[i]) pri.emplace_back(i),phi[i]=i-1;
		for(auto j:pri){
			if(i*j>n) break;
			isp[i*j]=1;
			if(i%j==0){
				phi[i*j]=phi[i]*j;
				break;
			}
			phi[i*j]=phi[i]*phi[j];
		}
	}
	rt[2]=rt[4]=1;
	for(auto i:pri){
		if(i==2) continue;
		for(int j=i;j<=n;j*=i) rt[j]=1;
		for(int j=i<<1;j<=n;j*=i) rt[j]=1;
	}
}
void divide(int x){
	v.clear();
	for(auto i:pri){
		if(i*i>x) break;
		if(x%i==0){
			v.emplace_back(i);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) v.emplace_back(x);
}
int power(int a,int b,int p){
	int res=1;
	for(;b;a=a*a%p,b>>=1)if(b&1)res=res*a%p;
	return res;
}
bool chk(int g,int m){
	if(power(g,phi[m],m)!=1) return 0;
	for(auto i:v) if(power(g,phi[m]/i,m)==1) return 0;
	return 1;
}
int fnd(int m){
	for(int i=1;i<m;i++) if(chk(i,m)) return i;
	return 0;
}
void got(int g,int m){
	ans.clear();
	int res=1;
	for(int i=1;i<=phi[m];i++){
		res=res*g%m;
		if(__gcd(phi[m],i)==1) ans.emplace_back(res);
	}
}

signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	init(1e6);
	cin>>T;
	while(T--){
		cin>>n>>d;
		if(!rt[n]) cout<<"0\n\n";
		else{
			divide(phi[n]);
			got(fnd(n),n);
			sort(ans.begin(),ans.end());
			cout<<ans.size()<<'\n';
			for(int i=d-1;i<(int)ans.size();i+=d) cout<<ans[i]<<' ';
			cout<<'\n';
		}
	}
	return 0;
}

指標(biāo)

定義

又稱離散對(duì)數(shù)，實(shí)際上就是模意義下的對(duì)數(shù)運(yùn)算。設(shè) \(m\in\mathbf N^*\) 且有原根 \(g\)，\(a\in\mathbf Z\) 且與 \(m\) 互質(zhì)，則必存在唯一的 \(0\le k<\varphi(m)\)，使得

則稱 \(k\) 為以 \(g\) 為底模 \(m\) 的 \(a\) 的指標(biāo)，記作 \(k=\gamma(a)\)。

指標(biāo)的求法等同于解一個(gè)形如 \(a^x\equiv b\pmod p\) 的高次同余方程，用 BSGS 求解即可。

性質(zhì)

• 若 \(a\equiv b\pmod m\)，則 \(\gamma(a)\equiv\gamma(b)\pmod{\varphi(m)}\)。
• \(\gamma(ab)\equiv\gamma(a)+\gamma(b)\pmod{\varphi(m)}\)。
• \(\gamma(a^n)\equiv n\gamma(a)\pmod{\varphi(m)}\)。