原根

定义

在数论，特别是整除理论中，原根是一个很重要的概念。

对于两个正整数 ， 由欧拉定理可知，存在正整数， 比如说欧拉函数，即小于等于的正整数中与互素的正整数的个数，使得 。

由此，在时，定义对模的指数        为使    成立的最小的正整数    。由前知     一定小于等于    ，若    ，则称    是模  的原根。

例子

设   ，则    等于6。

• 设    ，由于       ，而    ，所以 2 不是模 7 的一个原根。
• 设    ，由于    ，   ，   ，   ，   ，   ，因此有   ，所以 3 是模 7 的一个原根。

性质

• 可以证明，如果正整数   和正整数 d 满足 ，则   整除 d。因此  整除  。在例子中，当  时，我们仅需要验证 3 的 2、3 次方模 7 的余数即可，如果其中有一个是1，则3就不是原根。

• 记   ，则  模 m 两两不同余。因此当是模{\displaystyle m}的原根时，   构成模 m 的简化剩余系。

• 模  有原根的充要条件是  ，其中  是奇素数，  是任意正整数。

• 对正整数  ，如果 a 是模 m 的原根，那么 a 是整数模m乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zm×的一个生成元。由于Zm×有   个元素，而它的生成元的个数就是它的可逆元个数，即  个，因此当模  有原根时，它有  个原根。

一些数的原根列表

m	模m的原根(有*号的数没有原根，此时是有最大模m周期的数)	周期 ( A002322)
1	0	1
2	1	1
3	2	2
4	3	2
5	2, 3, 4	4
6	5	2
7	3, 5	6
8*	3, 5, 7	2
9	2, 5	6
10	3, 7	4
11	2, 6, 7, 8	10
12*	5, 7, 11	2
13	2, 6, 7, 11	12
14	3, 5	6
15*	2, 7, 8, 13	4
16*	3, 5, 11, 13	4
17	3, 5, 6, 7, 10, 11, 12, 14	16
18	5, 11	6
19	2, 3, 10, 13, 14, 15	18
20*	3, 7, 13, 17	4
21*	2, 5, 10, 11, 17, 19	6
22	7, 13, 17, 19	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22
24*	5, 7, 11, 13, 17, 19, 23	2
25	2, 3, 8, 12, 13, 17, 22, 23	20
26	7, 11, 15, 19	12
27	2, 5, 11, 14, 20, 23	18
28*	3, 5, 11, 17, 19, 23	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28
30*	7, 13, 17, 23	4
31	3, 11, 12, 13, 17, 21, 22, 24	30
32*	3, 5, 11, 13, 19, 21, 27, 29	8
33*	2, 5, 7, 8, 13, 14, 17, 19, 20, 26, 28, 29	10
34	3, 5, 7, 11, 23, 27, 29, 31	16
35*	2, 3, 12, 17, 18, 23, 32, 33	12
36*	5, 7, 11, 23, 29, 31	6

除了直接运算以外，至今还没有一个办法可以找到模特定m时的原根，但假如已知模m有一个原根，则可找出它其他的原根。

题目一：求最小的原根

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn = 1e6+10;
const int N = 1e8+10;
int prime[Maxn];//存储素数
int sprime[Maxn];//存储P-1的素因子
bool check[Maxn];
bitset<Maxn>pri;//结果只有0和1，判断是否为素数
int k;//记录Maxn以内的素数个数
int cnt;//记录素因子的个数
void is_prime(){
    pri.set();//将所有的二进制数都标为1
    for(int i=2; i<Maxn; i++) {
        if(pri[i]) {
            prime[k++]=i;
            for(int j=i+i; j<Maxn; j+=i)
                pri[j]=0;
        }
    }
}
void Divide(int n)//将n分解为素因子
{
    cnt=0;
    int t=(int)sqrt(1.0*n);
    for(int i=0; prime[i]<=t; i++) {
        if(n%prime[i]==0) {
            sprime[cnt++]=prime[i];
            while(n%prime[i]==0)//因为有可能有多个peime[i]
                n/=prime[i];
        }
    }
    if(n>1)
        sprime[cnt++]=n;//可能只有自己一个素因子
}
LL modexp(LL a,LL b,int mod)//快速幂取余
{
    LL res=1;
    while(b>0) {
        a=a%mod;
        if(b&1)
            res=res*a%mod;
        b=b>>1;
        a=a*a%mod;
    }
    return res;
}

int main()
{
    int p;
    Is_prime();
    while(~scanf("%d",&p)) {
        Divide(p-1);
        for(int g=2; g<p; g++) {
            int flag=1;
            for(int i=0; i<cnt; i++) {
                int t=(p-1)/sprime[i];
                if(modexp(g,t,p)==1) {
                    flag=0;
                    break;
                }
            }
            if(flag) {
                int root=g;
                printf("%d\n",root);
                break;//去掉break的话是求所有的原根，加上break是求最小的原根、
            }
        }
    }
    return 0;
}

题目二：求原根的个数

#include<bits/stdc++.h>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))

typedef long long ll;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;

ll n;
ll get(ll n){
    ll ans = n;
    for(int i=2;i*i<=n;i++){
        if(n %i == 0){
            ans = ans / i * (i - 1);
            while(n %i == 0)
                n /= i;
        }
    }
    if(n > 1)   ans = ans / n * (n - 1);
    return ans ;
}
int main(){
    while(scanf("%lld",&n)!=EOF){
        printf("%lld\n",get(get(n)));
    }
    return 0;
}