阶

  要定义原根，先要引入数论中阶的概念。

阶的定义

  设 $a,m\in {\mathbb{N}}^{+}$，且 $a\perp m$，使 $a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 成立的最小正整数 $x$，称为 $a$ 模 $m$ 的阶，记为 ${\text{ord}}_{m}a$。

阶的性质

  说明：描述阶的性质时，默认 $a,m\in {\mathbb{N}}^{+}$，且 $a\perp m$，即 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a$ 存在。
  性质1 $a^n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 的充要条件为 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a|n$。
  证明 设 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a=x$。
  首先证明充分性。设 $n=px$，其中 $p\in {\mathbb{N}}^{+}$。则 $a^n\equiv a^{px}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$；即 $a^n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  接下来证明必要性。设 $n=px+q$，其中 $p\in {\mathbb{N}}^{+}$ ，且 $0\le q<x,q\in \mathbb{N}$。则 $a^n\equiv a^{px+q}\equiv a^q\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，得到 $a^q\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，由于 $x$ 是满足 $a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 的最小正整数，又 $0\le q<x$，所以 $q=0$，故 $x\mid n$。
  证毕。
  推论1 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\mid \phi (m)$。
  证明  由欧拉定理，$a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，故 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\mid \phi (m)$。
  性质2 设 $b\in {\mathbb{N}}^{+}$，若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 ${\text{ord}}_{m}a={\text{ord}}_{m}b$。
  证明  首先 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，可以设 $b=a+km,k\in \mathbb{Z}$。则 $\gcd (b,m)=\gcd (a+km,m)$，由欧几里得算法 $\gcd (b,m)=\gcd (m,a)=1$，故 $b\perp m$，所以 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$ 存在。
  接下来用反证法证明 ${\text{ord}}_{m}a={\text{ord}}_{m}b$。假设 ${\text{ord}}_{m}a=x$，${\text{ord}}_{m}b=y$，且 $x\ne y$。则 $a^x\equiv (b-km{)}^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，将 $(b-km{)}^x$ 用二项式定理展开，得到 $b^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。根据假设 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b=y$，故 $x>y$。然而，$b^y\equiv (a+km{)}^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，将 $(a+km{)}^y$ 用二项式定理展开，得到 $a^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$；由于 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a=x$，故 $x<y$，产生矛盾；所以，$x=y$，即 ${\text{ord}}_{m}a={\text{ord}}_{m}b$。
  证毕。
  性质3 设 $p,q\in \mathbb{N}$，$a^p\equiv a^q(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 的充要条件为 $p\equiv q(\mathrm{m}\mathrm{o}\mathrm{d}{\text{ord}}_{m}a)$。
  证明 首先证明充分性。设 $p=k_1{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a+r$，$q=k_2{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a+r$，其中 $k_1,k_2,r\in \mathbb{N}$，且 $0\le r<{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a$。则 $a^p\equiv a^{k_1{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a+r}\equiv a^r(\mathrm{m}\mathrm{o}\mathrm{d}m)$，同理，$a^q\equiv a^r(\mathrm{m}\mathrm{o}\mathrm{d}m)$，故 $a^p\equiv a^q(\mathrm{m}\mathrm{o}\mathrm{d}m)$。充分性得证。
  接下来证明必要性。不妨设 $p\ge q$，则 $a^{p-q}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。根据性质1，${\text{ord}}_{a}m\mid p-q$，所以 $p\equiv q(\mathrm{m}\mathrm{o}\mathrm{d}{\text{ord}}_{m}a)$。必要性得证。
  证毕。
  性质4 令 ${\text{ord}}_{m}a=x$，则 $1,a,a^2,\cdots ,a^{x-1}$，模 $m$ 两两不同余。
  证明 下面用反证法证明。
  假设 $\exists i,j\in \mathbb{N}$ 且 $0\le j<i<x$，使得 $a^i\equiv a^j(\mathrm{m}\mathrm{o}\mathrm{d}m)$。故 $a^{i-j}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，由阶的定义，$i-j\ge x$，与 $0\le j<i<x$ 矛盾。故假设错误。
  证毕。
  性质5 设 $b\in {\mathbb{N}}^{+}$，若 $ab\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 ${\text{ord}}_{m}a={\text{ord}}_{m}b$。
  证明  令 ${\text{ord}}_{m}a=x$，${\text{ord}}_{m}b=y$，则有 $a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，$b^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  $a^x{b}^x\equiv b^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，由阶的定义 $x\ge y$。$a^y{b}^y\equiv a^y\equiv 1$，由阶的定义，$x\le y$。所以，$x=y$。
  证毕。
  性质6 令 $x={\text{ord}}_{m}a$，有 $t\in {\mathbb{N}}^{+}$ 则 ${\text{ord}}_m{a}^t=\frac{x}{\gcd (t,x)}$。
  证明 令 ${\text{ord}}_m{a}^t=k$，根据阶的定义，有 $a^{kt}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  由性质1，$x\mid kt$，故 $\frac{x}{\gcd (t,x)}\mid \frac{t}{\gcd (t,x)}k$ 。根据最大公约数的性质，$\frac{x}{\gcd (t,x)}\perp \frac{t}{\gcd (t,x)}$，所以 $\frac{x}{\gcd (t,x)}\mid k$。
  根据阶的定义，$k$ 为满足 $\frac{x}{\gcd (t,x)}\mid k$ 的最小正整数，故 $k=\frac{x}{\gcd (t,x)}$。
  证毕。
  性质7 设 $w\in {\mathbb{N}}^{+}$，若 $w\mid m$，则 ${\text{ord}}_{w}a\mid {\text{ord}}_{m}a$。
  证明 由阶的定义，$a^{{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$；因此，$a^{{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a}=km+1$，$k\in \mathbb{N}$。因为 $w\mid m$，所以 $a^{{\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}w)$。根据性质1，${\text{ord}}_{w}a\mid {\text{ord}}_{m}a$。
  证毕。
  性质8 设 $n\in {\mathbb{N}}^{+}$。若 $m\perp n,a\perp n$，则 ${\text{ord}}_{mn}a=\text{lcm}({\text{ord}}_{m}a,{\text{ord}}_{n}a)$。
  证明 令 $x={\text{ord}}_{mn}a$，$y=\text{lcm}({\text{ord}}_{m}a,{\text{ord}}_{n}a)$。
  根据阶的定义，$a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}mn)$，于是有 $a^x=kmn+1$，$k\in \mathbb{M}$；故 $a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，$a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$。由性质1，$ \text{ord}_ma\mid x$ 且 ${\text{ord}}_{n}a\mid x$，故 $\text{lcm}({\text{ord}}_{m}a,{\text{ord}}_{n}a)\mid x$，即 $y\mid x$。
  由最小公倍数的定义，有 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\mid y{\text{ord}}_{n}a\mid y$。根据性质1，有 $a^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 且 $a^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$；令 $a^y=k_{1}m+1=k_{2}n+1$，$k_1,k_2\in \mathbb{N}$，即 $k_{1}m=k_{2}n$。因为 $m\perp n$，故 $k_1=kn,k_2=km$，$k\in \mathbb{N}$，所以 $a^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}mn)$。再次根据性质1，有 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{mn}a\mid y$，即 $x|y$。
  综上所述，$x=y$，即 ${\text{ord}}_{mn}a=\text{lcm}({\text{ord}}_{m}a,{\text{ord}}_{n}a)$。
  证毕。
  性质9 设 $b\in {\mathbb{N}}^{+}$，若 $b\perp m$ 且 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\perp {\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$，则 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}ab={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\times {\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$ 。
  证明 令 $x={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a$，$y={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$，$z={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}ab$。由阶的定义，有 $a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，$b^y\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，$(ab{)}^z\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  由 $(ab{)}^z\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，得 $a^z\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 且 $b^z\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。根据性质1，$x\mid z$ 且 $y\mid z$，故 $\mathrm{l}\mathrm{c}\mathrm{m}(x,y)\mid z$。因为 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\perp {\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$，即 $x\perp y$；所以 $\mathrm{l}\mathrm{c}\mathrm{m}(x,y)=xy$，即 $xy\mid z$。
  因为 $x={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a$ 且 $y={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$，所以 $(ab{)}^{xy}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。根据性质1，$z\mid xy$。
  综上所述，$z=xy$，即 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}ab={\mathrm{o}\mathrm{r}\mathrm{d}}_{m}a\times {\mathrm{o}\mathrm{r}\mathrm{d}}_{m}b$。
  证毕。

原根

原根的定义

  设 $g,m\in {\mathbb{N}}^{+}$，且 $g\perp m$；若 ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m}g=\phi (m)$，则称 $g$ 是模 $m$ 的原根。

原根存在定理

  不加证明地给出：模 $m$ 有原根的充要条件是 $m=2,4,p^k,2p^k$，其中 $p$ 是奇素数，$k$ 是任意正整数。

原根判定定理

  不加证明地给出：若 $g$ 为模 $m$ 的原根，则对于任意 $\phi (m)$ 的质因子 $p$，必有 $g^{\frac{\phi (m)}{p}}\not\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。

求所有原根

  定理 设 $g$ 为模 $m$ 的原根，则集合 S = { g s ∣ 1 ≤ s ≤ φ ( m ) , s ⊥ φ ( m ) } S=\{g^{s} \mid 1 \leq s \leq \varphi(m),s\bot\varphi(m)\} S={ gs∣1≤s≤φ(m),s⊥φ(m)} 给出模 $m$ 的全部原根。模 $m$ 的原根有 $\phi (\phi (m))$ 个。
  略证 由原根的判定定理，对于任意 $\phi (m)$ 的质因子 $p$，有 $g^{\frac{\phi (m)}{p}}\not\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$；因此，${\left(g^s\right)}^{\frac{\phi (m)}{p}}\equiv {\left(g^{\phi (m)}\right)}^{\frac{s}{p}}(\mathrm{m}\mathrm{o}\mathrm{d}m)$。若 $\gcd (s,\phi (m))>1$，则存在一个 $p$，使得 $p\mid s$；此时，${\left(g^{\phi (m)}\right)}^{\frac{s}{p}}\equiv g^{k\phi (m)}(\mathrm{m}\mathrm{o}\mathrm{d}m)$，$k\in {\mathbb{N}}^{+}$；根据欧拉定理 $g^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$。因此，当且仅当 $s\perp \phi (m)$，$g^s$ 才为模 $m$ 的原根。
  若 $s>\phi (m)$，由扩展欧拉定理，则 $g^s\equiv g^{s\mathrm{m}\mathrm{o}\mathrm{d}\phi (m)}(\mathrm{m}\mathrm{o}\mathrm{d}m)$，转化为 $1\le s\le \phi (m)$ 的问题。
  根据欧拉函数定义，满足条件 $1\le s\le \phi (m),s\perp \phi (m)$ 的 $s$ 有 $\phi (\phi (m))$ 个。根据阶的性质4，这 $\phi (\phi (m))$ 个原根模 $m$ 两两不同余。
  可以证明，最小原根是不大于 $\sqrt[4]{m}$ 级别的。因此，不妨枚举 $[1,\sqrt[4]{m}]$ 的整数，得到最小原根 $g$，这样的时间是可以接受的；接着，再枚举 $g^s$ 的指数 $s$，若 $s$ 与 $\phi (m)$ 互质，则 $g^s\mathrm{m}\mathrm{o}\mathrm{d}m$ 为一个原根。

51Nod 1135 原根 $\looparrowright$

  给出一个质数 $P$，找出 $P$ 最小的原根。

输入

  输入一个质数 $P$$(3\le P\le 10^9)$。

输出

  输出 $P$ 最小的原根。

讯享网

输入样例

3

输出样例

2

分析

  从 $1$ 开始枚举可能的原根，根据原根判定定理检验：对于任意 $\phi (P)$ 的质因子 $p$，有 $g^{\frac{\phi (P)}{p}}\not\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}P)$。
  由欧拉函数的性质，$P$ 为质数，故 $\phi (P)=P-1$。

代码

#include<iostream> #include<vector> #define ll long long using namespace std; vector<ll>prime_factor; ll P; //-------------------------------- //分解质因数 void divide(ll x) { 
    ll i; for(i=2;i*i<=x;i++) { 
    if(x%i==0) { 
    prime_factor.push_back(i); while(x%i==0) x/=i; } } if(x>1) prime_factor.push_back(i); } //----------------------------------- //----------------------------------- //若P为质数 //φ(P)=P-1 inline ll phi(ll p) { 
   return p-1;} //----------------------------------- //----------------------------------- //快速幂 inline ll qpow_mod(ll a,ll b,ll mod) { 
    ll res=1; while(b) { 
    if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } //------------------------------------ int main() { 
    cin>>P; divide(phi(P)); ll i,j; for(i=1;;i++)//枚举 { 
    bool is=1; //遍历P-1的所有质因子 for(j=0;j<prime_factor.size();j++) { 
    if(qpow_mod(i,phi(P)/prime_factor[j],P)==1) { 
    is=0; break; } } if(is)//满足条件 { 
    cout<<i<<endl; return 0; } } } 

HDU Primitive Roots 4992 $\looparrowright$

Problem Description

  We say that integer $x$, $0<x<n$, is a primitive root modulo $n$ if and only if the minimum positive integer $y$ which makes $x^y=1(\mathrm{m}\mathrm{o}\mathrm{d}n)$ true is $\phi (n)$ . Here $\phi (n)$ is an arithmetic function that counts the totatives of $n$, that is, the positive integers less than or equal to $n$ that are relatively prime to $n$. Write a program which given any positive integer $n$$(2\le n<1000000)$, outputs all primitive roots of $n$ in ascending order.

Input

  Multi test cases.
  Each line of the input contains a positive integer $n$. Input is terminated by the end-of-file separator.

Output

  For each $n$, outputs all primitive roots of $n$ in ascending order in a single line, if there is no primitive root for $n$ just print $-1$ in a single line.

Sample Input

Sample Output

Idea

  首先根据原根存在定理判断原根是否存在。
  若原根存在，枚举 $[1,\sqrt[4]{n}]$ 的整数，得到最小原根 $g$；接着，再枚举 $g^s$ 的指数 $s$，若 $s$ 与 $\phi (n)$ 互质，则 $g^s\mathrm{m}\mathrm{o}\mathrm{d}n$ 为一个原根；若找到的原根已经达到 $\phi (\phi (n))$ 个，就可以停止枚举。

Code

讯享网#include<cstdio> #include<vector> #include<algorithm> #define ll long long #define N  using namespace std; int cnt;//质数个数 bool vis[N];//vis[i]=1表示i为合数 int prime[N>>1];//质数 int phi[N];//欧拉函数 vector<int>prime_factor;//质因子 vector<int>ans;//所有模n的原根 //------------------------------------------------------- //欧拉筛线性得到欧拉函数 void get_phi(int n) { 
    phi[1]=1; int i,j; for(i=2;i<=n;i++) { 
    if(!vis[i]) { 
    phi[i]=i-1; prime[++cnt]=i; } for(j=1;j<=cnt&&i*prime[j]<=n;j++) { 
    vis[i*prime[j]]=1; if(i%prime[j]==0) { 
    phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } //------------------------------------------------------- //------------------------------------------------------- //快速幂 inline int qpow_mod(ll a,int b,int mod) { 
    ll res=1; while(b) { 
    if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } //------------------------------------------------------- //------------------------------------------------------- //分解质因数 inline void divide(int x) { 
    int i; for(i=2;i*i<=x;i++) { 
    if(x%i==0) { 
    prime_factor.push_back(i); while(x%i==0) x/=i; } } if(x>1) prime_factor.push_back(x); } //------------------------------------------------------- //------------------------------------------------------- //利用原根存在定理 bool exist(int n) { 
    if(n==2||n==4) return 1; if(n%2==0) n/=2;//猜测为奇素数幂的二倍 int i; //检验是否为奇素数的幂 for(i=2;prime[i]<=n;i++) { 
    if(n%prime[i]==0) { 
    while(n%prime[i]==0) n/=prime[i]; //若n存在原根 //i为唯一质因子 return n==1; } } return 0; } //------------------------------------------------------- //------------------------------------------------------- int main() { 
    get_phi();//预处理1~的欧拉函数 int n; while(~scanf("%intd",&n)) { 
    //首先检验n是否存在原根 if(exist(n)) { 
    prime_factor.clear(); ans.clear(); //对phi[n]分解质因数 divide(phi[n]); int i,j; int g; //--------------------------------------------------------- //找到最小原根g for(i=1;;i++) { 
    bool is=1; if(__gcd(i,n)!=1) continue;//i不存在模n的阶 for(j=0;j<prime_factor.size();j++) { 
    //-------------------------------------------------- //原根判定 //对phi[n]的所有质因子p //i^(phi[n]/p)%n!=1; if(qpow_mod(i,phi[n]/prime_factor[j],n)==1) { 
    is=0; break; } //-------------------------------------------------- } if(is)//找到最小原根 { 
    g=i; break; } } //--------------------------------------------------------- //--------------------------------------------------------- //枚举指数s //若s与phi[n]互质 //g^s为原根 int s; ll power=1; for(s=1;ans.size()<phi[phi[n]];s++) { 
    power=power*g%n; if(__gcd(phi[n],s)==1) ans.push_back(power); } sort(ans.begin(),ans.end()); //--------------------------------------------------------- for(i=0;i<ans.size();i++) { 
    if(i) putchar(' '); printf("%d",ans[i]); } putchar('\n'); } else puts("-1"); } return 0; }