原根与阶

luoguhandongheng · 2026-02-26 16:11:49 · 算法·理论

广告。

对于 a 与模数 p，若 (a, p) = 1，由欧拉定理可知 a^{\varphi(p)} \equiv 1 \pmod p。因此存在最小的正整数 k 使得 a^k \equiv 1\pmod p。我们称其为 a 在模 p 意义下的阶，记作 \delta_p(a)。对于 (a, p)\ne 1 的情况，可以证明不存在这样的 k。而原根，是满足 \delta_p(x) = \varphi(p) 的所有数 x。

原根与阶的定义天然地把我们的研究范围限制在缩系之中，这也是十分自然地，因为只有缩系中的数有逆元，是 (\mathbb{Z} / p\mathbb{Z})^{\times} 中的结构。接下来我们将认识到，这一乘法群多多少少有循环的结构，至于是否为循环群，等价于其是否存在原根，而原根恰为这一循环群的生成元。

我们下面给出一些阶的性质，他们大都是比较显然的：

2. 对于 n，若 a^n \equiv 1 \pmod p 成立，当且仅当 \delta_p(a) \mid n。
3. \delta_p(a^k) = \frac{[\delta_p(a), k]}{k} = \frac{\delta_p(a)}{(\delta_p(a), k)}

原根个数定理

对于 p 来说，其既约剩余系中有 \varphi(p) 个数。假设其存在原根 g，根据上面的性质 1，g^0, g^1, \cdots, g^{\varphi(p) - 1} 模 p 互不同余。也就是说，从 g^0 = 1 开始，我们不断乘 g，刚好可以遍历整个既约剩余系。这就是生成元的含义，即自己的幂次可以生成整个群。

下面，我们考虑这个缩系中阶为 \varphi(p) 的数有几个，即有几个原根。整个缩系是一个 \varphi(p) 的环。我们发现每个数都可以写成 g^k 的形式，而乘一次 g^k 相当于一次的步长是 k，从 g^0 开始走，要求遍历所有点，就要求间隔 (\varphi(p), k) = 1，也就是满足条件的 k 有 \varphi(\varphi(p)) 个。进一步地，考虑阶为 d 的数有几个，由上可知首先要求 d \mid \varphi(p)，然后这次相当于在一个长度为 d 的小环上走，我们把小环看作大环，那么照样有 \varphi(d) 个不同的步长满足条件。

原根存在定理

我们先需要重提一下 CRT，它事实上阐释了下面的事情：

其中 m = a \times b 且 a,b 互质。这是什么意思呢，就相当于我们把 m 剩余系中的数投影到了 a,b 两维上，或者说确定了 a,b 两维的坐标我们就确定了这个数在 m 这个坐标系中的位置（正是 CRT 给出的构造解）。进一步地，这个性质也可也扩展到乘法群上。

有什么用呢？它让我们能合并两个循环群。比如 a,b 均有原根，我们就可以讨论 ab 是否有原根。下面给出结论：对于循环群 C_n, C_m，C_n \times C_m 是循环群 \iff (n, m) = 1。证明也是简单的，C_n \times C_m 有 n \times m 个元素，也就是说需要存在阶为 nm 的元素，而我们现在只有阶为 [n, m] 的元素，因此需要 [n, m] = nm，也即 (n, m) = 1。

接着我们终于能说明怎样的数存在原根了：

正整数 n 存在原根 \iff n = 2, 4, p^k, 2p^k，其中 p 是非 2 的素数且 k \ge 1。

必要性：

2. 首先我们说明 $n = p$ 有原根。\ 假设存在一个阶为 $d$ 的数 $g$，设其生成的循环子群为 $\langle g\rangle$，它的阶也是 $d$，这个 $d$ 首先满足 $d \mid p - 1$。与上面的个数定理相同，$\langle g\rangle$ 中同样存在 $\varphi(d)$ 个数的阶是 $d$。而我们知道 $x^d \equiv 1 \pmod p$ 的解至多 $d$ 个，而 $\langle g \rangle$ 已经提供了 $d$ 个。因此可以说明，所有阶为 $d$ 的元素都是方程的根，也都是 $\langle g \rangle$ 中元素，正好有 $\varphi(d)$ 个。这也就是说，阶为 $d$ 的元素要么为 $\varphi(d)$ 要么为 $0$。\ 而我们知道 $\sum_{d \mid (p - 1)} \varphi(p) = p - 1$，而缩系之中正好就有 $p - 1$ 个元素。由于阶为 $d$ 的集合之间两两不交，因此每个 $d$ 都必须取到 $\varphi(d)$ 而不能是 $0$，否则就凑不出 $p - 1$ 个数了。这就说明了，一定存在阶为 $p - 1$ 的数，且有 $\varphi(p - 1)$ 个。\ 接着说明 $n = p^k (k\ge 2)$ 有原根的部分，~~由于笔者自己还不会~~，也与前文关系不大，欢迎大家移步[这一篇](https://www.luogu.com.cn/article/py24mb57)来看。
3. 此时 $(\mathbb{Z} / n\mathbb{Z})^{×} \cong (\mathbb{Z} / 2\mathbb{Z})^{×}\times(\mathbb{Z} / p^k\mathbb{Z})^{×}$，后面二者都是循环群，并且二者的阶的最大公因数 $(\varphi(2), \varphi(p^k)) = 1$，因此前者也是循环群，也存在原根。

充分性:

1. 事实上此时对于 $(\mathbb{Z}/n\mathbb{Z})^{\times} \cong C_2 \times C_{2^{k - 2}}$。这是因为 $(\mathbb{Z}/n\mathbb{Z})^{\times}$ 中首先有阶为 $2$ 的元素 $-1$，同时还有阶为 $2^{k - 2}$ 的元素 $5$，他们两者生成子群的交为 $\{1\}$。需要注意的是 $-1$ 并不属于 $5$ 的生成子群，因为下面我们将看到 $5$ 的生成子群中阶为 $2$ 的元素（上面的个数定理告诉我们只有一个）是 $5^{2^{k - 3}} \equiv 1 + 2^{k - 1}$ 在 $k\ge 3$ 时 $\not\equiv -1 \pmod{2^k}$。这就刚好覆盖了所有 $2^{k - 1}$ 个数。而我们知道，这两个循环群阶的 gcd 为 $2$ 并不互质，因此直积后不是一个循环群。\ 下面我们说明 $5$ 的阶是 $2^{k - 2}$。这是因为对 $k\ge 3,5^{2^{k - 3}} \equiv 1 + 2^{k - 1} \not\equiv 1 \pmod {2^k}$，而 $5^{2^{k-2}} \equiv (1 + 2^{k - 1})^2 \equiv 1 \pmod {2^k}$。\ 那么现在就要说明对 $k\ge 3,5^{2^{k - 3}} \equiv 1 + 2^{k - 1}$。我们设 $m = 2^{k - 3}$，可知 $5^m = (1 + 4)^m = \sum_{i = 0}^{m}{m \choose i}4^i$。对 $i = 0$ 的项，贡献了 $1$；对 $i = 1$ 的项，代入得贡献了 $2^{k - 1}$；对 $i \ge 2$ 的项，我们希望说明其为 $2^k$ 的倍数。\ 那么考虑算 $\nu_2({m \choose i}4^i) = 2i + \nu_2({m \choose i}) = 2i + \nu_2(m!) - \nu_2(i!) - \nu_2((m - i)!)$，我们需要该式 $\ge k$。接着由 Legendre 定理，原式后三项等于 $(m - S_2(m)) -(i - S_2(i)) - (m - i - S_2(m - i))=S_2(i) + S_2(m - i) - 1$。\ 我们接着设 $t = \nu_2(i)$，也即 $i = 2^t \times r$，其中 $r$ 是奇数。那么 $S_2(m - i) = S_2((m - 1) - i + 1)$。注意到 $(m - 1) - i$ 是 $i$ 的所有二进制位取反后的结果（$m$ 是二的幂次），再 $+1$ 之后，其原本最后末位 $t$ 个 $0$ 取反成 $1$ 后加 $1$ 又全都变回了 $0$，然后最后第 $t + 1$ 位上变成了 $1$。所以 $S_2(m - i) = k - 3 - S_2(i) - t + 1 = k - 2 - S_2(i) - t$。\ 带回最开始的原式，得到 $\nu_2({m \choose i}4^i)= 2i + S_2(i) + (k - 2 - S_2(i) - t) - 1=k-3-\nu_2(i)+2i$。当 $i = 2$ 时，原式等于 $k$。当 $i = 3$ 时，原式等于 $k + 3$。对于 $i \ge 4$，此时 $2i-\nu_2(i) \ge 2i - \log_2(i) \ge 2 \times 4 - 2 = 6$，原式就 $\ge k + 3$。这样就证完了。
2. 我们将其设为 $p, q$。由于 $C_{p^r} \times C_{q^o}$ 的阶分别为 $(p - 1)p^{r - 1}$，$(q - 1)q^{o - 1}$ 必然有公因数 $2$。因此其不为循环群。
3. 思路同上，显然 gcd 不为 1。

求解原根

一个结论是说如果 p 存在原根，则其最小原根 g 是 O(p^{0.25})。因此我们只需要从小到大枚举 g，并快速地检验 g 是否是原根。接下来我们设 m = \varphi(p)，枚举所有 k < m 并检验 g^k \not\equiv 1 太慢了。事实上由于所有数的阶 d \mid m，我们只需要检验 m 的所有真因数即可，进一步地，只需要把所有 m 的素因子 r 拿出来，检验 k = \frac{m}{r} 的情况即可。如果他们都不等于 1，就说明 g 是一个原根。

接下来我们考虑从一个原根找出所有 \varphi(m) 个原根。枚举 g^i，如果 (i, m) = 1，就说明以 i 的步长在环上走可以走遍，于是我们就把 g^i 丢进原根集合里即可。 那么就可以通过这道模板题。 ::::info[Code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, V = 1e6;
int T, n, d, phi[N], pri[N], cnt, f[N];
bitset<N> vis, fl;
void init(){
    phi[1] = 1;
    for(int i = 2; i <= V; ++i){
        if(!vis[i]){
            pri[++cnt] = i;
            phi[i] = i - 1;
            f[i] = i;
        }
        for(int j = 1; j <= cnt; ++j){
            if(i * pri[j] > V) break;
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0){
                f[i * pri[j]] = f[i] * pri[j];
                phi[i * pri[j]] = (pri[j] - 1) * f[i] * phi[i / f[i]];
                break;
            }
            f[i * pri[j]] = pri[j];
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
    fl[2] = fl[4] = 1;
    for(int i = 2; i <= cnt; ++i){
        for(int k = pri[i]; k <= V; k *= pri[i]){
            if(2 * k <= V) fl[2 * k] = 1;
            fl[k] = 1;
        }
    }
}
int qpow(int a, int b, int mod){
    int ret = 1;
    for(; b; b >>= 1, a = a * a % mod){
        if(b & 1) ret = ret * a % mod;
    }
    return ret;
}
bool check(int g, int n){
    int x = phi[n];
    for(int o = 2; o <= x; ++o){
        if(x % o == 0){
            while(x % o == 0) x /= o;
            if(qpow(g, phi[n] / o, n) == 1) return 0;
        }
    }
    return qpow(g, phi[n], n) == 1;
}
void solve(){
    cin >> n >> d;
    if(!fl[n]) cout << 0 << "\n\n";
    else{
        cout << phi[phi[n]] << '\n';
        int g; 
        for(int i = 1; i < n; ++i){
            if(check(i, n)){
                g = i;
                break;
            }
        }
        vector<int> rge;
        int x = g;
        for(int i = 1; i <= phi[n]; ++i, x = x * g % n){
            if(__gcd(i, phi[n]) == 1) rge.push_back(x);
        }
        sort(rge.begin(), rge.end());
        for(int i = d - 1; i < rge.size(); i += d)
            cout << rge[i] << ' ';
        cout << '\n';
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    init();
    cin >> T;
    while(T--) solve();
    return 0;
}

::::