原根
阶：设 (a, m in mathbb{N}^{+},) 且 (a perp m,) 使 (a^{x} equiv 1(mod m)) 成立的最小正整数 (x,) 称为 (a) 模 (m) 的阶, 记为 (operatorname{ord}_{m} a_{0})
原根：设 (g, m in mathbb{N}^{+},) 且 (g perp m ;) 若 (operatorname{ord}_{m} g=varphi(m),) 则称 (g) 是模 (m) 的原根。
定义原根的意义在于, 原根非常类似于单位根, 故有一些很好的性质, 比如说我们考虑当 (m) 是质数时, 原根有如下等价定义：若 (g) 是模 (m) 的原根, 则 (g^{1}, g^{2}, cdots, g^{m-1}) 的值在模 (m) 的意义下两两不同, 注意到模(m)剩余系中恰有(m)个数，而任意一个非零数的幂次都不可能等于0，故原根的幂次在模(m)的剩余系中是最稠密的，换句话说，仅用原根就能够充分表示模 (m) 剩余系的性质。
个数性质
如果模m有原根，那么原根恰有$ varphi(varphi(m))$个。
一个比较通俗的证明：
剩余系是加法群，约化剩余系是乘法群。
在剩余系中，可逆元是与模数 m互质的数（可能不是叫可逆元，反正大概了解一下定义就行），所以其个数为 (varphi(m),) 并且可逆元在加法的意义上可以取遍剩余系, 也就是说如果令 (q) 为可逆元, 那么 (q, 2 q, cdots, m q) 在模 (m) 的意义下可以取遍整个剩余系。
约化剩余系由可逆元所组成的，并且原根在乘法的意义上可以取遍约化剩余系，也就是说假设 (g) 为模 (m) 意义下的一个原根, 那么 (g^{1}, g^{2}, cdots, g^{varphi(m)}) 在模 (m) 的意义下可以取遍整个约化剩余系, 可见原根一定 属于约化剩余系, 所以我们首先应该在约化剩余系的 (varphi(m)) 个数里寻找。
观察 (g^{1}, g^{2}, cdots, g^{varphi(m)},) 我们想知道其中有多少数是能在乘法的意义下取遍模 (m) 的整个约化剩余系, 根据乘法中指数相加以及扩展欧拉定理, 我们可以将问题转化成求 (0,1, cdots, varphi(m)-1) 中有多少数在 加法的意义下能取遍模 (varphi(m)) 的剩余系, 这样就变成了求模 (varphi(m)) 的剩余系中可逆元的个数, 也就是说 模 (m) 的意义下原根的个数为 (varphi(varphi(m))) 个。
存在定理
定理 1: 质数 (P) 一定有原根, 且恰有 (varphi(P-1)) 个原根，实际上, 当且仅当 (m=2,4, P^{k}, 2 P^{k}) 时(k为任意正整数), (m) 才有原根。
判定定理
若 (g) 为模 (m) 的原根, 则对于任意 (varphi(m)) 的质因子 (p,) 必有 (g^{frac{varphi(m)}{p}} ot equiv 1(mod m))
求所有原根
定理：设 (g) 为模 (m) 的原根, 则集合 (S=left{g^{s} mid 1 leq s leq varphi(m), s perp varphi(m) ight}) 是模 (m) 的所有原根。
可以证明, 最小原根是不大于 (sqrt[4]{m}) 级别的。因此, 不妨枚举 ([1, sqrt[4]{m}]) 的整数, 得到最小原根 (g), 这样的时间是可以接受的; 接着，再枚举 (g^{s}) 的指数 (s,) 若 (s) 与 (varphi(m)) 互质, 则 (g^{s} mod m) 为一个原根。
具体步骤：
1.首先判断是否有原根
方法：这个数必须是2,4, (p^{a}, 2 p^{a})
2.求第一个原根
方法：从1枚举到 (m^{0.25},) 设当前数为 (i_{circ}) 如果 ((mathrm{i}, mathrm{m})=1) 。
且对于 (varphi(m)) 的所有质因子, 都有 (i ^{varphi(m) / prime} mod m) 不等于1.
那么得到最小的原根(g)
3.求所有原根
方法：从1枚举到 (varphi(m)),设当前数为i。若(i, (varphi(m))=1) 。则 (g^{i}) 也是一个原根。
代码:
//P6091，给定n,d,求出有c个原根，输出c
,ans[d],ans[2d]....ans[c/d*d]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
bool isPrime[maxn];
int Prime[maxn], primecnt = 0;
int phi[maxn];
void getPrime(int n){
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
phi[1] = 1;
for(int i = 2; i <= n; i++){
if(isPrime[i]){
Prime[++primecnt] = i;
phi[i]=i-1;
}
for(int j = 1; j <= primecnt && i*Prime[j] <= n; j++) {
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0){
phi[i*Prime[j]]=phi[i]*Prime[j];
break;
}
else{
phi[i*Prime[j]]=phi[i]*(Prime[j]-1);
}
}
}
}
ll fp(ll b,ll p,ll mod){
ll ans=1;
while(p){
if(p&1)ans=ans*b%mod;
b=b*b%mod;
p>>=1;
}
return ans;
}
bool check(int x){
for(int i=1;i<=primecnt;i++){
if(x%Prime[i]==0){
while(x%Prime[i]==0)x/=Prime[i];
if(x==2||x==1)return 1;
else return 0;
}
}
}
bool check2(int x,int n){
vector<int>pfacphi;
int temp=phi[n];
for(int i=1;i<=primecnt;i++){
if(temp%Prime[i]==0){
pfacphi.push_back(Prime[i]);
while(temp%Prime[i]==0)temp/=Prime[i];
}
if(temp<Prime[i]*Prime[i])break;
}
if(temp>1)pfacphi.push_back(temp);
for(auto b:pfacphi){
if(fp(x,phi[n]/b,n)==1){
return 0;
}
}
return 1;
}
int main () {
getPrime(maxn-5);
int T;
scanf("%d",&T);
while(T--){
int n,d;
scanf("%d%d",&n,&d);
if(!isPrime[n] && n!=2 && n!=4 && !check(n) && (n%2!=0 || !check(n/2))){
puts("0
");continue;
}
int g;
for(int i=1;i<=n;i++){
if(__gcd(i,n)!=1)continue;
if(check2(i,n)){
g=i;break;
}
}
vector<int>ans;
ll temp=1;
for(int i=1;i<=phi[n];i++){
temp=temp*g%n;
if(__gcd(i,phi[n])==1)ans.push_back(temp);
}
sort(ans.begin(),ans.end());
printf("%d
",ans.size());
for(int i=d-1;i<ans.size();i+=d){
if(i>d-1)printf(" ");
printf("%d",ans[i]);
}
puts("");
}
}
求单个原根
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e2+5;
ll m;
ll fac[maxn], cnt;
ll quickPower(ll a, ll b, ll M) {
ll ans = 1ll;
ll base = a;
while (b) {
if (b & 1) {
ans *= base;
ans %= M;
}
base *= base;
base %= M;
b >>= 1;
}
return ans;
}
void get_fac(ll x) {
x--;
ll m = sqrt(x) + 0.5;
for (int i = 2; i <= m; i++) {
if (x % i == 0) fac[cnt++] = i;
while (x % i == 0) x /= i;
}
if (x > 1) fac[cnt++] = x;
}
int main() {
scanf("%lld", &m);
get_fac(m);
for (ll g = 2; g < m; g++) {
int f = 1;
for (int j = 0; j < cnt; j++) {
if (quickPower(g, (m - 1) / fac[j], m) == 1ll) {
f = 0;
break;
}
}
if (f) {
printf("%d", g);
break;
}
}
}