原根

阶

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

阶的定义

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

阶的性质

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

原根

原根的定义

设 $g,m\in\mathbb N^+$，且 $g\bot m$；若 $\mathrm{ord}_mg=\varphi(m)$，则称 $g$ 是模 $m$ 的原根。

原根存在定理

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

原根判定定理

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

求所有原根

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

51Nod 1135 原根 $\looparrowright$

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

输入

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

输出

输出 $P$ 最小的原根。

输入样例

3

输出样例

2

分析

从 $1$ 开始枚举可能的原根，根据原根判定定理检验：对于任意 $\varphi(P)$ 的质因子 $p$，有 $g^{\frac{\varphi(P)}{p}}\not\equiv 1 \pmod P$。
由欧拉函数的性质，$P$ 为质数，故 $\varphi(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 \pmod n$ true is $φ(n)$ . Here $φ(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

4
25

Sample Output

3
2 3 8 12 13 17 22 23

Idea

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

Code

#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
#define N 1000002
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(1000000);//预处理1~1000000的欧拉函数
	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;
}