定义:设,,使得成立的最小的,称为对模的阶,记为。
定理:如果模有原根,那么它一共有个原根。
定理:若,,,则。
定理:如果为素数,那么素数一定存在原根,并且模的原根的个数为。
定理:设是正整数,是整数,若模的阶等于,则称为模的一个原根。
假设一个数对于模来说是原根,那么的结果两两不同,且有,那么可以称为是模的一个原根,归根到底就是当且仅当指数为的时候成立。(这里是素数)
模有原根的充要条件:,其中是奇素数。
求模素数原根的方法:对素因子分解,即是的标准分解式,若恒有
成立,则就是的原根。(对于合数求原根,只需把换成即可)
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include <bitset> using namespace std; typedef long long LL; const int N = 1000010; bitset<N> prime; int p[N],pri[N]; int k,cnt; void isprime() { prime.set(); for(int i=2; i<N; i++) { if(prime[i]) { p[k++] = i; for(int j=i+i; j<N; j+=i) prime[j] = false; } } } void Divide(int n) { cnt = 0; int t = (int)sqrt(1.0*n); for(int i=0; p[i]<=t; i++) { if(n%p[i]==0) { pri[cnt++] = p[i]; while(n%p[i]==0) n /= p[i]; } } if(n > 1) pri[cnt++] = n; } LL quick_mod(LL a,LL b,LL m) { LL ans = 1; a %= m; while(b) { if(b&1) { ans = ans * a % m; b--; } b >>= 1; a = a * a % m; } return ans; } int main() { int P; isprime(); while(cin>>P) { Divide(P-1); for(int g=2; g<P; g++) { bool flag = true; for(int i=0; i<cnt; i++) { int t = (P - 1) / pri[i]; if(quick_mod(g,t,P) == 1) { flag = false; break; } } if(flag) { int root = g; cout<<root<<endl; } } } return 0; }