原根学习笔记
原根
这是一个又臭又长的内容。
拉格朗日定理：设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式
\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\nmid a_n) \]的同余方程 \(f(x)\equiv 0\pmod p\) 在模 \(p\) 意义下至多有 \(n\) 个不同解。
证明：使用归纳法，对于 \(n=0\) 时，由于 \(p\nmid a_0\)，所以 \(f(x)\equiv 0\pmod p\) 无解，定理对 \(n=0\) 的多项式 \(f(0)\) 都成立。
若命题对于 \(n< x\) 均成立，采用反证法，假设当 \(n=x\) 时有至少 \(x+1\) 个解 \(x_0,x_1,\cdots,x_n\)。不妨设 \(f(x)-f(x_0)=(x-x_0)g(x)\)，则 \(g(x)\) 在模 \(p\) 意义下是一个至多 \(n-1\) 次的多项式。因为当 \(x=x_1,x_2,\cdots,x_n\) 时，\(f(x)\equiv 0\pmod p\)，所以
\[(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)=f(x_i)\equiv 0\pmod p \]从而 \(g(x)\equiv 0\pmod p\) 至少有 \(n\) 个根，与归纳假设矛盾。
所以定理对 \(n\) 次多项式也成立，得证。
阶：由欧拉定理可知，对 \(a\in \mathbb{Z},m\in\mathbb{N}^*\)，若 \(\gcd(a,m)=1\)，则
\[a^{\varphi(m)}\equiv 1\pmod m \]因此满足同余式 \(a^n\equiv 1\pmod m\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。
原根：设 \(m\in\mathbb{N}^*,a\in\mathbb{Z}\)。若 \(\gcd(a,m)=1\)，且 \(\delta_m(a)=\varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。
关于阶有一个较为显然的性质：
若 \(a^n\equiv 1\pmod m\)，则 \(\delta_m(a)\mid n\)。
证明：对 \(n\) 除以 \(\delta_m(a)\) 作带余除法，设
\[n=\delta_m(a)q+r,0\le r<\delta_m(a) \]若 \(r>0\)，则
\(a^r\equiv a^r(a^{\delta_m(a)})^q\equiv a^n\equiv 1\pmod m\)
这与 \(\delta_m(a)\) 的最小性矛盾。故 \(r=0\)，即 \(\delta_m(a)\mid n\)。
关于阶还有两个重要的性质：
性质 \(1\)：设 \(m\in\mathbb{N}^*,a,b\in\mathbb{Z},\gcd(a,m)=\gcd(b,m)=1\)，则
\[\delta_m(ab)=\delta_m(a)\delta_m(b) \]的充要条件是 \(\gcd(\delta_m(a),\delta_m(b))=1\)。
证明：必要性：有 \(a^{\delta_m(a)}\equiv 1\pmod m\) 及 \(b^{\delta_m(b)}\equiv 1\pmod m\)，可知
\[(ab)^{\text{lcm}(\delta_m(a),\delta_m(b))}\equiv 1\pmod m \]由前面所述的性质，有
\[\delta_m(ab)\mid \text{lcm}(\delta_m(a),\delta_m(b)) \]有由于 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\)，所以
\[\delta_m(a)\delta_m(b)\mid \text{lcm}(\delta_m(a),\delta_m(b)) \]所以 \(\gcd(\delta_m(a),\delta_m(b))=1\)。
充分性：由 \((ab)^{\delta_m(ab)}\equiv 1\pmod m\) 可知
\[1\equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)}\pmod m \]故 \(\delta_m(a)\mid\delta_m(ab)\delta_m(b)\)。结合 \(\gcd(\delta_m(a),\delta_m(b))=1\) 即得
\[\delta_m(a)\mid\delta_m(ab) \]对称地，可得
\[\delta_m(b)\mid\delta_m(ab) \]所以
\[\delta_m(a)\delta_m(b)\mid\delta_m(ab) \]另一方面，有
\[(ab)^{\delta_m(a)\delta_m(b)}\equiv (a^{\delta_m(a)})^{\delta_m(b)}(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1\pmod m \]故
\[\delta_m(ab)\mid\delta_m(a)\delta_m(b) \]综合即可得到 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\)。
性质 \(2\)：设 \(k\in\mathbb{N},m\in\mathbb{N}^*,a\in\mathbb{Z},\gcd(a,m)=1\)，则
\[\delta_m(a^k)=\frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]
证明：注意到
\[a^{k\delta_m(a^k)}=(a^k)^\delta_m(a^k)\equiv 1\pmod m\\ \Rightarrow \delta_m(a)\mid k\delta_m(a^k)\\ \Rightarrow \frac{\delta_m(a)}{\gcd(\delta_m(a),k)}\mid\delta_m(a^k) \]另一方面，由 \(a^{\delta_m(a)}\equiv 1\pmod m\) 可知
\[(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv 1\pmod m \]所以
\[\delta_m(a^k)\mid\frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]综合可得 \(\delta_m(a)=\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)。
接下来讨论什么样的 \(m\) 存在原根。
首先，对于 \(m=2,4\)，显然存在原根。
定理 \(1\)：对于奇素数 \(p\)，\(p\) 存在原根。
证明：先证明一个引理：
引理：设 \(a\) 与 \(b\) 是与 \(p\) 互素的两个整数，则存在 \(c\in\mathbb{Z}\) 使得 \(\delta_p(c)=\text{lcm}(\delta_p(a),\delta_p(b))\)。
证明：记 \(r=\delta_m(a),t=\delta_m(b)\)，设它们的标准分解为（只要求 \(\max(\alpha_i,\beta_i)>0\)）
\[r=\prod_{i=1}^{s}p_i^{\alpha_i},t=\prod_{i=1}^{s}p_i^{\beta_i} \]令 \(l\) 为所有 \(\alpha_i\le\beta_i\) 的 \(p_i^{\alpha_i}\) 的乘积，\(m\) 为所有 \(\beta_i<\alpha_i\) 的 \(p_i^{\beta_i}\) 的乘积。记\(r=lx,t=my\)，则 \(\gcd(x,y)=1,\text{lcm}(r,t)=xy\)。
由性质 \(2\)，\(\delta_p(a^l)=x,\delta_p(b^m)=y\)，则由性质 \(1\)，\(\delta_p(a^lb^m)=xy=\text{lcm}(\delta_p(a),\delta_p(b))\)，取 \(c=a^lb^m\) 即可。
对 \(1\) ～ \(p-1\) 依次两两使用引理，可知存在 \(g\in\mathbb{Z}\) 使得
\[\delta_p(g)=\text{lcm}(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)) \]这表明 \(\delta_p(j)\mid \delta_p(g)\)，所以 \(j=1,2,\cdots,p-1\) 都是同余方程
\[x^{\delta_p(g)}\equiv 1\pmod p \]的根。有拉格朗日定理可知，\(\delta_p(g)\ge p-1\)。又由费马小定理，易知 \(\delta_p(g)\le p-1\)，所以 \(\delta_p(g)=p-1=\varphi(p)\)。所以 \(g\) 为 \(p\) 的原根。
定理 \(2\)：对于奇素数 \(p\)，\(\alpha\in\mathbb{N}^*\)，\(p^{\alpha}\) 有原根。
证明：先证明一个引理。
引理：存在模 \(p\) 的原根 \(g\)，使得 \(g^{p-1}\not\equiv 1\pmod {p^2}\)。
证明：事实上，仍取模 \(p\) 的原根 \(g\)，若 \(g\) 不满足条件，我们认定 \(g+p\) 满足条件。易知 \(g+p\) 也是模 \(p\) 的原根。
于是有
\[\begin{aligned}(g+p)^{p-1}&\equiv g^{p-1}+(p-1)pg^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv1\pmod {p^2}\end{aligned} \]
接着，我们证明若 \(g\) 是一个满足引理条件的原根，则对于任意 \(\alpha\in\mathbb{N}^*\)，\(g\) 是模 \(p^{\alpha}\) 的原根。
首先证明下面的结论：对于任意 \(\beta\in\mathbb{N}^*\)，都可设
\[g^{\varphi(p^\beta)}=1+p^{\beta}k_\beta \]不难发现当 \(\beta=1\) 时结论成立，现设上式对 \(\beta\) 成立，则
\[\begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^\beta)})^p\\&=(1+p^\beta k_\beta)^p\\&\equiv 1+p^{\beta+1}k_\beta\end{aligned} \]结合 \(p\nmid k_\beta\) 可知结论成立。
所以命题对 \(\beta\in\mathbb{N}^*\) 都成立。
其次，记 \(\delta=\delta_{p^\alpha}(g)\)，则有欧拉定理，可知 \(\delta\mid p^{\alpha-1}(p-1)\)。
而由 \(g\) 为模 \(p\) 的原根，及 \(g^\delta\equiv1\pmod {p^\alpha}\) 可知 \((p-1)\mid \delta\)。
所以可设 \(\delta=p^{\beta-1}(p-1)(1\le\beta\le\alpha)\)。利用之前的结论可知
\[g^{\varphi(p^\beta)}\not\equiv1\pmod {p^{\beta+1}}\Rightarrow g^\delta\not\equiv1\pmod {p^{\beta+1}} \]结合 \(g^\delta\equiv 1\pmod {p^\alpha}\) 可知 \(\beta\ge\alpha\)。所以 \(\beta=\alpha\)，即
\[\delta_{p^\alpha}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha) \]从而 \(g\) 是 \(p^\alpha\) 的原根。
定理 \(3\)：对于奇素数 \(p\)，\(\alpha\in\mathbb{N}^*\)，\(2p^\alpha\) 有原根。
证明：设 \(g\) 是模 \(p^\alpha\) 的原根，则 \(g+p^\alpha\) 也是模 \(p^\alpha\) 的原根。
在 \(g\) 和 \(g+p^\alpha\) 中有一个是奇数，设其为 \(G\)，则 \(\gcd(G,2p^\alpha)=1\)。
由欧拉定理，\(\delta_{2p^\alpha}(G)\mid\varphi(2p^\alpha)\)。
而 \(G^{\delta_{2p^\alpha}(G)}\equiv 1\pmod{2p^\alpha}\)，故 \(G^{\delta_{2p^\alpha}(G)}\equiv 1\pmod{p^\alpha}\)。
利用 \(G\) 为模 \(p^\alpha\) 的原根可知 \(\varphi(p^\alpha)\mid\delta_{2p^\alpha}(G)\)。
结合 \(\varphi(p^\alpha)=\varphi(2p^\alpha)\) 可知 \(G\) 为模 \(2p^\alpha\) 的原根。
定理 \(4\)：对于 \(m\not\in\{2,4,p^\alpha,2p^\alpha\}\)，则对于任意 \(a\in\mathbb{Z}\)，都有 \(\delta_m{a}<\varphi(m)\)，即模 \(m\) 的原根不存在。
证明：对于 \(m=2^\alpha,\alpha\in\mathbb{N}^{*},\alpha\ge 3\)，则对于任意奇数 \(a=2k+1\) 有
\[\begin{aligned}a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\&\equiv 1+2^{\alpha-2}(2k)+2^{\alpha-1}(2^{\alpha-2}-1)k^2\\&\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k)\\&\equiv1\pmod{2^\alpha} \end{aligned} \]若 \(m\) 不是 \(2\) 的次幂，则设 \(m=rt\) 满足 \(2<r<t,\gcd(r,t)=1\)。则由欧拉定理可知
\[a^{\varphi(r)}\equiv1\pmod{r},a^{\varphi(t)}\equiv 1\pmod{t} \]当 \(n>2\) 时，\(\varphi(n)\) 为偶数，所以
\[a^{\frac{\varphi(r)\varphi(t)}{2}}\equiv1\pmod{rt} \]所以 \(\delta_m(a)\le\frac{\varphi(r)\varphi(t)}{2}=\frac{\varphi(rt)}{2}=\frac{\varphi(m)}{2}<\varphi(m)\)。
上述定理阐述了原根的充要条件，即除了 \(2,4,p^\alpha,2p^\alpha\) 次方以外，其他的数都没有原根。于是我们可以与处理素数即其幂次，\(O(1)\) 判断是否有原根。
如果一个数有原根，可以先求出其最小原根。事实上，\(m\) 的最小原根是不多于 \(m^{\frac{1}{4}}\) 级别的。根据这个结论，我们可以直接从小到大枚举。根据原根的定义，若 \(g\) 为模 \(m\) 的原根，则对于 \(\varphi(m)\) 的任意素因数 \(p\)，必有
\[g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m \]同时，只要满足如上条件的 \(g\) 一定是原根。于是我们可以与处理出 \(\varphi(m)\) 的所有质因数，通过快速幂来判断。
假如找到了一个原根 \(g\)，不难证明对于所有 \(\gcd(x,\varphi(m))=1\) 的 \(x\)，\(g^x\) 均为原根，所以模 \(m\) 的原根有 \(\varphi(\varphi(m))\) 个，所以我们可以在找到 \(g\) 后再枚举找出所有 \(m\) 的原根。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
int T,n,d,tot,cnt,sum;
int p[N],phi[N],fc[N];
ll ans[N];
bool rt[N],vis[N];
void Euler(int x){
phi[1]=1;
for(int i=2;i<=x;i++){
if(!vis[i]){
p[++tot]=i;
phi[i]=i-1;
}
for(int j=1;p[j]<=x/i;j++){
vis[i*p[j]]=true;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
rt[1]=rt[2]=rt[4]=true;
for(int i=2;i<=tot;i++){
for(int j=1;j<=x/p[i];j*=p[i])rt[j*p[i]]=true;
for(int j=2;j<=x/p[i];j*=p[i])rt[j*p[i]]=true;
}
return ;
}
int Gcd(int a,int b){
return b==0?a:Gcd(b,a%b);
}
ll QuickPow(ll a,int b,int p){
ll res=1;
while(b>0){
if((b&1)==1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
void Fac(int x){
cnt=0;
for(int i=1;p[i]<=x/p[i];i++){
if(p[i]>x)break ;
if(x%p[i]==0){
fc[++cnt]=p[i];
while(x%p[i]==0)x/=p[i];
}
}
if(x>1)fc[++cnt]=x;
return ;
}
bool Check(int x,int p){
if(QuickPow(x,phi[p],p)!=1)return false;
for(int i=1;i<=cnt;i++){
if(QuickPow(x,phi[p]/fc[i],p)==1)return false;
}
return true;
}//检验是否是原根
int FindRt(int x){
for(int i=1;i<x;i++){
if(Check(i,x))return i;
}
return 0;
}//找最小原根
void GetRt(int x,int p){
ll res=1;
sum=0;
for(int i=1;i<=phi[p];i++){
res=res*x%p;
if(Gcd(i,phi[p])==1)ans[++sum]=res;
}
return ;
}//处理所有原根
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>T;
Euler(N-5);//预处理质数、phi、有无原根
while(T--){
cin>>n>>d;
if(rt[n]){
Fac(phi[n]);//预处理质因数
GetRt(FindRt(n),n);//找最小原根后找所有原根
sort(ans+1,ans+sum+1);
cout<<sum<<"\n";
for(int i=1;i<=sum/d;i++)cout<<ans[i*d]<<" ";
cout<<"\n";
}else cout<<"0\n\n";//直接判断没有原根
}
return 0;
}