定義：設
，
，使得
成立的最小的
，稱為
對模
的階，記為
。
定理：如果模
有原根，那麼它一共有
個原根。
定理：若
，
，
，則
。
定理：如果
為素數，那麼素數
一定存在原根，并且模
的原根的個數為
。
定理：設
是正整數，
是整數，若
模
的階等于
，則稱
為模
的一個原根。
假設一個數
對于模
來說是原根，那麼
的結果兩兩不同,且有
，那麼
可以稱為是模
的一個原根，歸根到底就是
當且僅當指數為
的時候成立。（這裡
是素數）
模
有原根的充要條件：
，其中
是奇素數。
求模素數
原根的方法：對
素因子分解，即
是
的标準分解式，若恒有
成立，則
就是
的原根。（對于合數求原根，隻需把
換成
即可）
#include <iostream>
#include <stdio.h>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
long long d[1000];
long long dp[1000];
int kuai(long long x,long long n,long long m)
{
long long i,j;
long long s=1;
for(i=0;;i++)
{
long long t=x;
long long d=n%2;n=n/2;
if(d==0) t=1;
if(d!=0)
{
if(i==0) t=t*1%m;
else
{
for(j=0;j<i;j++)
t=t*t%m;
}
}
s=s*t%m; if(n==0) break;
}
return s;
}
int main()
{
long long p;
while(cin>>p)
{
long long k=p-1;
long long i;
long long x=1;
d[0]=k;
d[1]=1;
if(k%2==0)
{
d[2]=2;
while(k%2==0) k=k/2;
}
long long l=3;
for(long long j=3;j<=k;j+=2)
{
if(k%j==0)
{
d[l]=j;l++;
while(k%j==0) k=k/j;
//cout<<j<<endl;
}
}
for(i=2;i<=p;i++)
{
long long z=1;
for(long long j=2;j<l;j++)
{
long long t=(p-1)/d[j];
long long r=kuai(i,t,p);
//cout<<r<<' '<<t<<' '<<d[j]<<' '<<i<<endl;
if(r==1) {z=0;break;}
}
if(z==1) {cout<<i<<endl;break;}
}
}
}