1 阶
1.1 定义
由欧拉定理可知，对于 \(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)\)。
1.2 性质
只要扯到数学性质和证明这部分内容就会极其恶臭。
性质 1：
\(a,a^2,\cdots a^{\delta_m(a)}\) 模 \(m\) 两两不同余。
证明：考虑反证。若存在 \(i,j\) 使得 \(a^i\equiv a^j\pmod m\)，则 \(a^{|i-j|}\equiv 1\pmod m\)。但是 \(\delta_m(a)\) 是最小的满足 \(a^n\equiv 1\pmod m\) 的 \(n\)，所以 \(|i-j|\) 不可能满足该条件，矛盾，故原命题成立。
性质 2：
若 \(a^{n}\equiv 1\pmod m\)，则 \(\delta_m(a)\mid n\)。
证明：设 \(n=k\delta_m(a)+r,0\le r<\delta_m(a)\)，那么会有：
\[a^n\equiv a^{k\delta_m(a)+r}\equiv a^{k\delta_m(a)}\times a^r\equiv a^r\equiv 1\pmod m \]所以 \(a^r\equiv 1\)，但是 \(\delta_m(a)\) 是满足 \(a^n\equiv 1\pmod m\) 的最小 \(n\)，所以 \(r\) 只可能等于 \(0\)，于是 \(\delta_m(a)\mid n\)。
据此性质可有以下推论：若 \(a^p\equiv a^q\pmod m\)，则 \(p\equiv q\pmod {\delta_m(a)}\)。
性质 3：
设 \(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 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(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\) 可得 \((ab)^{\delta_m(ab)\times \delta_m(b)}\equiv a^{\delta_m(ab)\times \delta_m(b)}\equiv 1\pmod m\)。
故 \(\delta_m(a)\mid \delta_m(ab)\times \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)\times\delta_m(b)\mid \delta_m(ab)\)。
另一方面有 \((ab)^{\delta_m(a)\times \delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1\pmod m\)。所以 \(\delta_m(ab)\mid \delta_m(a)\times \delta_m(b)\)。
于是 \(\delta_m(ab)=\delta_m(a)\times \delta_m(b)\)。
性质 4：
设 \(k\in\mathbb N,m\in\mathbb N^+,a\in \mathbb Z,\gcd(a,m)=1\)，则
\[\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]证明：
由 \((a^k)^{\delta_m(a^k)}\equiv 1\pmod m\) 可得 \(a^{k\times \delta_m(a^k)}\equiv 1\pmod m\)，于是 \(\delta_m(a)\mid k\times \delta_m(a^k)\)。故 \(\tfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}\mid \delta_m(a^k)\)。
由 \(a^{\delta_m(a)}\equiv 1\pmod m\) 可得 \((a^k)^{\tfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}}\equiv (a^{\delta_m(a)})^{\tfrac{a^k}{\gcd(\delta_m(a),k)}}\equiv 1\pmod m\)。故 \(\delta_m(a^k)\mid \tfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)。
于是 \(\delta_m(a^k)=\tfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)。
2 原根
2.1 定义
设 \(m\in \mathbb N^+,g\in \mathbb Z\)，若 \(\gcd(m,g)=1\)，且 \(\delta_m(g)=\varphi(m)\)，称 \(g\) 为模 \(m\) 的原根。
当 \(m\) 为质数时，由阶的性质 1 可得，此时 \(g^i(0<i<m)\) 模 \(m\) 两两不同余。
2.2 原根判定定理
设 \(m\in \mathbb N^+,g\in \mathbb Z\)，若 \(\gcd(m,g)=1\)，则 \(g\) 为模 \(m\) 的原根的充要条件是，对于 \(\varphi(m)\) 的任意一个质因子 \(p\)，都满足 \(g^{\frac{\varphi(m)}p}\not\equiv 1\pmod m\)。
证明：必要性显然，如果存在则说明 \(\delta_m(g)\) 不是最小的 \(n\)，矛盾。
充分性考虑反证，假设存在一个 \(p\)，满足对于 \(\varphi(m)\) 的任意一个质因子 \(p\)，都满足 \(g^{\frac{\varphi(m)}p}\not\equiv 1\pmod m\)，但是 \(g\) 不是 \(m\) 的原根。那么由于 \(g^{\varphi(m)}\equiv 1\pmod m\)，会有 \(\delta_m(g)\mid \varphi(m)\)。
由于 \(g\) 不是 \(m\) 的原根，所以 \(\delta_m(g)\ne \varphi(m)\)，所以一定存在一个 \(\varphi(m)\) 的质因子 \(p\) 使得 \(\delta_m(g)\mid\tfrac{\varphi(m)}{p}\)，而这个质因子 \(p\) 就满足 \(g^{\frac{\varphi(m)}p}\equiv 1\pmod m\)，与条件矛盾。必要性得证。
2.3 原根个数
若一个数 \(m\) 有原根，则它的原根个数为 \(\varphi(\varphi(m))\) 个。
证明：
若 \(m\) 有原根 \(g\)，根据阶的性质 4 可得：
\[\delta_m(g^k)=\dfrac{\delta_m(g)}{\gcd(\delta_m(g),k)}=\dfrac {\varphi(m)}{\gcd(\varphi(m),k)} \]所以如果 \(\gcd(\varphi(m),k)=1\)，就会有 \(\delta_m(g^k)=\varphi(m)\)，此时 \(g^k\) 也是 \(m\) 的原根。 而这样的 \(k\) 有 \(\varphi(\varphi(m))\) 个，所以原根就有 \(\varphi(\varphi(m))\) 个。
2.4 原根存在定理
一个数 \(m\) 存在原根，当且仅当 \(m=2,4,p^k,2p^k\)，其中 \(p\) 是奇质数。
这个定理可以帮助我们用于判定一个数是否有原根，其证明较为复杂，在此不作详细叙述，可以看OI Wiki上的证明。
2.5 求原根
有了上面三个定理，找原根其实并不困难。我们首先判断该数字是否有原根，如果有暴力枚举最小原根 \(g\)，根据原根判定定理看其是否合法。如果是，用原根个数定理中的条件去找出剩下的 \(g^k\) 这些原根即可。
例题：【模板】原根，代码如下：
#include <bits/stdc++.h>
#define il inline
#define int long long
using namespace std;
const int Maxn = 1e6 + 5;
const int Inf = 2e9;
int T;
int n, d;
int prim[Maxn], tot, phi[Maxn];
int vis[Maxn];
int rt[Maxn];
void init(int N) {
phi[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) {
prim[++tot] = i;
phi[i] = i - 1;
}
for(int j = 1, x; (x = prim[j] * i) <= N; j++) {
vis[x] = 1;
if(i % prim[j] == 0) {
phi[x] = phi[i] * prim[j];
break;
}
phi[x] = phi[i] * (prim[j] - 1);
}
}
rt[2] = rt[4] = 1;
for(int i = 2; i <= tot; i++) {
for(int j = prim[i]; j <= N; j *= prim[i]) rt[j] = 1;
for(int j = 2 * prim[i]; j <= N; j *= prim[i]) rt[j] = 1;
}
}
int fac[Maxn], cnt;
void divd(int x) {
cnt = 0;
for(int i = 1; prim[i] <= x / prim[i]; i++) {
if(x % prim[i] == 0) {
fac[++cnt] = prim[i];
while(x % prim[i] == 0) x /= prim[i];
}
}
if(x > 1) fac[++cnt] = x;
}
int qpow(int a, int b, int p) {
int res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int check(int g, int m) {//判断是否是原根
if(qpow(g, phi[m], m) != 1) return 0;
for(int i = 1; i <= cnt; i++) {
if(qpow(g, phi[m] / fac[i], m) == 1) return 0;
}
return 1;
}
int findrt(int m) {//找最小原根
for(int i = 1; i < m; i++) {
if(check(i, m)) return i;
}
}
int ans[Maxn], ret;
void getrt(int g, int m) {//找出所有原根
int res = 1;
ret = 0;
for(int i = 1; i <= phi[m]; i++) {
res = res * g % m;
if(__gcd(phi[m], i) == 1) {
ans[++ret] = res;
}
}
}
void solve() {
cin >> n >> d;
if(rt[n]) {//判断是否有原根
divd(phi[n]);//分解质因数
getrt(findrt(n), n);//找出原根
sort(ans + 1, ans + ret + 1);
cout << ret << '\n';
for(int i = d; i <= ret; i += d) {
cout << ans[i] << " ";
}
cout << '\n';
}
else {
cout << "0\n\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
init(1e6);
while(T--) solve();
return 0;
}
3 指标
3.1 定义
指标，也被称作离散对数，实际上就是模意义下的对数运算。设 \(m\in\mathbb N^+\) 且有原根 \(g\)，对于满足 \(\gcd(a,m)=1\) 的整数 \(a\)，必存在唯一的 \(0\le k<\varphi(m)\)，使得
\[g^k\equiv a\pmod m \]称 \(k\) 为以 \(g\) 为底模 \(m\) 的离散对数，或者指标，记作 \(k=\text{ind}(a)\) 或 \(k=\gamma(a)\)。
指标的求法很简单，既然是离散对数，那么直接用 BSGS 算法即可。
3.2 性质
指标的性质与普通对数类似，下面列举几条。注意下式中 \(a,b\) 均满足 \(a,b\in\mathbb Z,\gcd(a,m)=\gcd(b,m)=1\)。
性质 1：
若 \(a\equiv b\pmod m\)，则 \(\gamma(a)\equiv \gamma(b)\pmod {\varphi(m)}\)。
该性质可以直接由阶的性质 2 中的推论得到。
性质 2：
\[\gamma(ab)\equiv \gamma(a)+\gamma(b)\pmod{\varphi(m)} \]证明：
\(g^{\gamma(ab)}\equiv ab\equiv g^{\gamma(a)}\times g^{\gamma(b)}\equiv g^{\gamma(a)+\gamma(b)}\pmod m\)。再由性质 1 可得 \(\gamma(ab)\equiv \gamma(a)+\gamma(b)\pmod {\varphi(m)}\)。
性质 3：
\[\gamma(a^n)\equiv n\gamma(a)\pmod {\varphi(m)} \]证明：对 \(\gamma(a^n)\) 做 \(n-1\) 次性质 2 即可。
4 例题
例 1 [BZOJ1420] Discrete Root
题意： 给定 \(k,a,p\)，求方程 \(x^k\equiv a\pmod p\) 的所有在 \([0,p-1]\) 内解，保证 \(p\) 为质数且 \(a<p\)。
既然 \(p\) 为质数，其一定存在原根 \(g\)。对方程做指标性质 1 可得 \(\gamma(x^k)\equiv \gamma(a)\pmod {\varphi(p)}\)。再由指标性质 3 可得 \(k\gamma(x)\equiv \gamma(a)\pmod {p-1}\)。注意到此时方程化为了一个朴素同余方程的形式，用 exgcd 求出 \(\gamma(x)\) 的所有解并代入求出对应 \(x\) 即可。
例 2 [BZOJ2219] 数论之神
题意：给定 \(A,B,K\)，求方程 \(x^A\equiv B\pmod {2K+1}\) 的所有在 \([0,2K]\) 内解。
上面一道题其实只是为了引出这道题的。发现此时模数变为 \(2K+1\)，没有保证是质数，所以不一定有原根，难以直接求解。
不过我们可以对 \(2K+1\) 做质因数分解，设 \(P=2K+1=\prod p_i^{\alpha_i}\)，那么原来的方程可以化为若干线性同余方程 \(x^A\equiv B\pmod {p_i^{\alpha_i}}\)。由于 \(2K+1\) 必为奇数，所以 \(p_i\) 一定是奇质数，所以 \(p_i^{\alpha_i}\) 必存在原根。
我们对于每一个方程可以求出一个 \(x_i\)，然后我们会发现只要最后的 \(x\) 对于所有方程满足 \(x\equiv x_i\pmod {p_i^{\alpha_i}}\)，那么这个 \(x\) 就是一个合法答案。不难发现这是一个线性同余方程组，根据中国剩余定理，可以知道满足条件的 \(x\) 在 \([0,P-1]\) 范围内只有一个。因此我们对每个方程求出它们解的个数再相乘就是最后答案。
那么现在的问题就是求 \(x^A\equiv B\pmod {p_i^{\alpha_i}}\) 的解的个数。由于此时不一定有 \(\gcd(B,p_i^{\alpha_i})=1\)，所以不能直接像上一道题一样用指标求解。所以分类讨论：
-
\(\gcd(B,p_i^{\alpha_i})=p_i^{\alpha_i}\) 时：
此时 \(p_i^{\alpha_i}\mid B\)，所以方程化为 \(x^A\equiv 0\pmod{p_i^{\alpha_i}}\)。设 \(x=a{p_i}^t(\gcd(a,p_i)=1)\)，代入有 \(a^Ap_i^{tA}\equiv 0\pmod {p_i^{\alpha_i}}\)。于是有 \(tA\ge \alpha_i\)，解得 \(t\ge\lceil\tfrac{\alpha_i}{A}\rceil\)。那么实际上只需要让 \(p_i^{\lceil\tfrac{\alpha_i}{A}\rceil}\mid x\) 即可，所以 \(x\) 取值有 \(p_i^{\alpha_i}/ p_i^{\lceil\tfrac{\alpha_i}{A}\rceil}=p_i^{\alpha_i-\lceil\tfrac{\alpha_i}{A}\rceil}\) 种。
-
\(\gcd(B,p_i^{\alpha_i})=1\) 时：
此时就与上一道题是一样的了，先求出指标 \(\gamma(B)\)，如果 \(\gcd(A,\varphi(p_i^{\alpha_i}))\mid \gamma(B)\)，那么取值就有 \(\gcd(A,\varphi(p_i^{\alpha_i}))\) 种。
-
\(\gcd(B,p_i^{\alpha_i})={p_i}^k\) 时：
令 \(B=b{p_i}^k\)，那么会有 \(x^A\equiv b{p_i}^k\pmod {p_i^{\alpha_i}}\)。显然此时如果有解，那么 \(x_A\) 中也必然有 \({p_i}^k\)。于是根据同余方程的消去律，可以得到 \(\dfrac{x^A}{{p_i}^k}\equiv b\pmod{p_i^{\alpha_i-k}}\)，第一项其实也就是 \(\left(\dfrac{x}{p_i^{\frac kA}}\right)^A\)。
那么此时 \(\gcd(b,p_i^{\alpha_i-k})\) 就等于 \(1\) 了，回到了情况 2。但是注意到此时求出来的 \(x\) 的取值范围是 \([0,{p_i}^{\alpha_i-k+\frac kA})\) 的，但是我们要求的范围是 \(x\in[0,p_i^{\alpha_i})\) 的，所以还需要给求出来的结果乘上 \({p_i}^{k-\frac kA}\) 。