原根-快速求解一个数的原根
1.原根定义欧拉定理（也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理表明，若为正整数，且互素（即），则

对模的指数

是模的原根

若存在，那么显然的事情否则，假设存在一个t<phi(x)=x-1使得a^t = 1 (mod x)那么由裴蜀定理，一定存在一组k,r使得kt=(x-1)r+gcd(t,x-1)而由欧拉定理有，a^(x-1) = 1 (mod x)于是1 = a^(kt) = a^(xr-r+gcd(t,x-1)) = a^gcd(t,x-1) (mod x)而t<x-1故gcd(t,x-1)<x-1又gcd(t,x-1)|x-1 于是gcd(t,x-1)必整除(x-1)/p1,(x-1)/p2...(x-1)/pm其中至少一个，设其一为(x-1)/pi那么a^((x-1)/pi) = (a^gcd(t,x-1))^s = 1^s = 1 (mod x)这与假设矛盾

代码：

来至http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135的一道题目：

题目设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）给出1个质数P，找出P最小的原根。输入1个质数P(3 <= P <= 10^9)输出P最小的原根。

解答

#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>using namespace std;int P;const int NUM = 32170;int prime[NUM/4];bool f[NUM];int pNum = 0;void getPrime()//线性筛选素数{for (int i = 2; i < NUM; ++ i){if (!f[i]){f[i] = 1;prime[pNum++] = i;}for (int j = 0; j < pNum && i*prime[j] < NUM; ++ j){f[i*prime[j]] = 1;if (i%prime[j] == 0){break;}}}}__int64 getProduct(int a,int b,int P)//快速求次幂mod{__int64 ans = 1;__int64 tmp = a;while (b){if (b&1){ans = ans*tmp%P;}tmp = tmp*tmp%P;b>>=1;}return ans;}bool judge(int num)//求num的所有的质因子{int elem[1000];int elemNum = 0;int k = P - 1;for (int i = 0; i < pNum; ++ i){bool flag = false;while (!(k%prime[i])){flag = true;k /= prime[i];}if (flag){elem[elemNum ++] = prime[i];}if (k==1){break;}if (k/prime[i]<prime[i]){elem[elemNum ++] = prime[i];break;}}bool flag = true;for (int i = 0; i < elemNum; ++ i){if (getProduct(num,(P-1)/elem[i],P) == 1){flag = false;break;}}return flag;}int main(){getPrime();while (cin >> P){for (int i = 2;;++i){if (judge(i)){cout << i<< endl;break;}}}return 0;}