阶
先看看啥是阶.
由欧拉定理可知,对于 \(a\in\mathbf{Z},m\in\mathbf{N}^*\) ,若 \((a,m)=1\) ,则 \(a^{\varphi(m)}\equiv1\pmod m\) .
因此满足同余式 \(a^n\equiv1\pmod m\) 的最小正整数 \(n\) 存在,这个 \(n\) 称作 \(a\) 模 \(m\) 的阶,记作 \(\delta_m(a)\) 或 \(\operatorname{ord}_m(a)\) .
再看看有啥性质.
- \(a,a^2,\dots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余.
- 若 \(a^n\equiv1\pmod m\) ,则 \(\delta_m(a)|n\) .
- 设 \(m\in\mathbf{N}^*,a\in\mathbf{Z},b\in\mathbf{Z},(a,m)=(b,m)=1\) ,
则 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\) 的充要条件为 \((\delta_m(a),\delta_m(b))=1\) .
- 证明必要性:
点击查看证明
易知 $a^{\delta_m(a)}\equiv1\pmod m,b^{\delta_m(b)}\equiv1\pmod m$ ,则 \((ab)^{[\delta_m(a),\delta_m(b)]}\equiv1\pmod m\) ,
可知 \(\delta_m(ab)|[\delta_m(a),\delta_m(b)]\) ,
又因为 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\) ,
所以 \(\delta_m(a)\delta_m(b)|[\delta_m(a),\delta_m(b)]\) ,
所以 \((\delta_m(a),\delta_m(b))=1\) .
- 证明充分性:
点击查看证明
易知 $(ab)^{\delta_m(ab)}\equiv1\pmod m$ ,则 \((ab)^{\delta_m(ab)}\equiv(ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)}\equiv1\pmod m\) ,
所以 \(\delta_m(a)|\delta_m(ab)\delta_m(b)\) ,
又因为 \((\delta_m(a),\delta_m(b))=1\) ,
所以 \(\delta_m(a)|\delta_m(ab)\) ,
同理 \(\delta_m(b)|\delta_m(ab)\) ,
所以 \(\delta_m(a)\delta_m(b)|\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)}\equiv1\pmod m\) ,
所以 \(\delta_m(ab)|\delta_m(a)\delta_m(b)\) ,
综上 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\) .
- 设 \(k\in\mathbf{N},m\in\mathbf{N}^*,a\in\mathbf{Z},(a,m)=1\) ,则 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{(\delta_m(a),k)}\) .
- 证明:
点击查看证明
注意到 $a^{k\delta_m(a^k)}\equiv (a^k)^{\delta_m(a^k)}\equiv1\pmod m$ ,则 \(\delta_m(a)|k\delta_m(a^k)\) ,即 \(\dfrac{\delta_m(a)}{(\delta_m(a),k)}|\delta_m(a^k)\) ,
又注意到 \((a^k)^{\frac{\delta_m(a)}{(\delta_m(a),k)}}\equiv(a^{\delta_m(a)})^{\frac{k}{(\delta_m(a),k)}}\equiv1\pmod m\) ,
则 \(\delta_m(a^k)|\dfrac{\delta_m(a)}{(\delta_m(a),k)}\) ,
综上 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{(\delta_m(a),k)}\) .
原根
说完阶,再看看啥是原根.
设\(m\in\mathbf{N}^*,g\in\mathbf{Z}\) .若 \((g,m)=1\) ,且 \(\delta_m(g)=\varphi(m)\)，则称 \(g\) 为模 \(m\) 的原根.
原根有什么性质呢?
- (原根判定定理)设 \(m\geqslant3,(g,m)=1\) ,则 \(g\) 是模 \(m\) 的原根的充要条件为,对于 \(\varphi(m)\) 的每个素因数 \(p\) ,都有 \(g^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m\)
- 证明充分性:
点击查看证明
使用反证法.当对于 \(\varphi(m)\) 的每个素因数 \(p\) ,都有 \(g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m\) 成立时,我们假设存在一个 \(g\),其不是模 \(m\) 的原根.
因为 \(g\) 不是 \(m\) 的原根,则存在一个 \(t<\varphi(m)\) 使得 \(g^t\equiv 1\pmod{m}\) .
由裴蜀定理得,一定存在一组 \(k,x\) 满足 \(kt=x\varphi(m)+(t,\varphi(m))\) .
又由欧拉定理得 \(g^{\varphi(m)}\equiv 1\pmod{m}\) ,故有:
\[1\equiv g^{kt}\equiv g^{x\varphi(m)+(t,\varphi(m))}\equiv g^{(t,\varphi(m))}\pmod{m} \]由于 \((t, \varphi(m)) \mid \varphi(m)\) 且 \((t, \varphi(m))\leqslant t < \varphi(m)\) .
故存在 \(\varphi(m)\) 的素因数 \(p\) 使得 \((t, \varphi(m)) \mid \frac{\varphi(m)}{p}\) .
则 \(g^{\frac{\varphi(m)}{p}}\equiv g^{(t, \varphi(m))}\equiv 1\pmod{m}\) ,与条件矛盾.
故假设不成立,原命题成立.
- (原根个数)若一个数 \(m\) 有原根,则它原根的个数为 \(\varphi(\varphi(m))\) .
- 证明:
点击查看证明
若 $m$ 有原根 $g$ ,则: \[\delta_m(g^k)=\dfrac{\delta_m(g)}{\left(\delta_m(g),k\right)}=\dfrac{\varphi(m)}{\left(\varphi(m),k\right)} \]所以若 \(\left(k,\varphi(m)\right)=1\) ,则有: \(\delta_m(g^k)=\varphi(m)\) ,即 \(g^k\) 也是模 \(m\) 的原根.
而满足 \(\left(\varphi(m),k\right)=1\) 且 \(1\leq k \leq \varphi(m)\) 的 \(k\) 有 \(\varphi(\varphi(m))\) 个.所以原根就有 \(\varphi(\varphi(m))\) 个.
- (原根存在定理)一个数 \(m\) 存在原根当且仅当 \(m=2,4,p^{\alpha},2p^{\alpha}\) ,其中 \(p\) 为奇素数, \(\alpha\in \mathbf{N}^{*}\) .
- 证明:
见 OI-Wiki .
- (最小原根的范围估计) 见 OI-Wiki .
题目
题单: https://vjudge.net/contest/638199 .
洛谷 P6081 【模板】原根
见 https://www.luogu.com.cn/article/d1yftjt7 .
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int t,p,cnt,tot,ctans,fc[MAXN],ans[MAXN],pri[MAXN],rt[MAXN],q[MAXN],phi[MAXN];
void init () {
phi[1]=1;
for (int i=2;i<=MAXN-10;i++) {
if (!q[i]) {pri[++tot]=i,phi[i]=i-1;}
for (int j=1;j<=tot&&pri[j]*i<=MAXN-10;j++) {
q[i*pri[j]]=1;
if (i%pri[j]==0) {
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
rt[2]=rt[4]=1;
for (int i=2;i<=tot;i++) {
for (int j=1;(1ll*j*pri[i])<=MAXN-10;j*=pri[i]) {rt[j*pri[i]]=1;}
for (int j=2;(1ll*j*pri[i])<=MAXN-10;j*=pri[i]) {rt[j*pri[i]]=1;}
}
return;
}
int gcd (int a,int b) {return (b==0?a:gcd(b,a%b));}
int qpow (int a,int b,int p) {
int res=1;
while (b) {
if (b&1) {res=(1ll*res*a)%p;}
a=(1ll*a*a)%p;
b>>=1;
}
return res;
}
void proc (int p) {
for (int i=2;i*i<=p;i++) {
if (p%i==0) {
fc[++cnt]=i;
while (p%i==0) {p/=i;}
}
}
if (p>1) {fc[++cnt]=p;}
return;
}
bool chk (int x,int p) {
if (qpow(x,phi[p],p)!=1) {return 0;}
for (int i=1;i<=cnt;i++) {
if (qpow(x,phi[p]/fc[i],p)==1) {return 0;}
}
return 1;
}
int findrt (int p) {
for (int i=1;i<p;i++) {
if (chk(i,p)) {return i;}
}
return 0;
}
void getrt (int p,int x) {
int prod=1;
for (int i=1;i<=phi[p];i++) {
prod=(1ll*prod*x)%p;
if (gcd(i,phi[p])==1) {
ans[++ctans]=prod;
}
}
return;
}
int main () {
init();
scanf("%d",&t);
for (int ii=1;ii<=t;ii++) {
int wtf;
scanf("%d%d",&p,&wtf);
if (rt[p]) {
ctans=cnt=0;
proc(phi[p]);
int mn=findrt(p);
getrt(p,mn);
sort(ans+1,ans+ctans+1);
printf("%d\n",ctans);
for (int i=1;i<=ctans/wtf;i++) {printf("%d ",ans[i*wtf]);}
printf("\n");
} else {
printf("0\n\n");
}
}
return 0;
}
POJ 1284 Primitive Roots
直接求 \(\varphi(\varphi(p))\) 即可.
点击查看代码
#include <iostream>
using namespace std;
const int N = 65536;
bool ok[N + 5];
int phi[N + 5], pri[N + 5], tot = 0;
void init() {
phi[1] = 1;
for (int i = 2; i <= N; i++) {
if (!ok[i]) {
pri[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; i * pri[j] <= N && j <= tot; j++) {
if (i % pri[j] == 0) {
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
ok[i * pri[j]] = true;
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init();
int p;
while (cin >> p)
cout << phi[phi[p]] << endl;
return 0;
}