阶与原根

阶

设 \(n > 1\) 且 \(a\) 是满足 \((a, n) = 1\) 的整数，则必定有一个 \(a^r \equiv 1 \pmod n\)，其中 \(r \in [1, n - 1]\)。

原因是 \(a^0, ...,a^{n - 1}\) 都与 \(n\) 互质，所以它们模 \(n\) 至多有 \(n - 1\) 个余数，因此必定存在 \(a^i \equiv a^j \pmod n\)，所以 \(a^{j - i} \equiv 1 \pmod n\)。

满足条件的最小正整数 \(r\) 称为 \(a\) 模 \(n\) 的阶。

一个性质是若 \(a\) 模 \(n\) 的阶为 \(r\) 且 \((a, n) = 1\)，那么对于正整数 \(m\) 满足 \(a^m \equiv 1 \pmod n\)，一定有 \(r | m\)，设 \(m = rq + k\) 可以证明。

进一步根据欧拉定理，\(r\) 一定整除 \(\varphi(n)\)，于是我们在求阶时可以直接枚举 \(\varphi(n)\) 的因数然后判定即可。

原根

若 \(a\) 模 \(m\) 的阶等于 \(\varphi(m)\)，则称 \(a\) 为 \(m\) 的原根。

原根存在定理

\(m\) 有原根当且仅当 \(m = 2, 4, p^{\alpha}, 2p^{\alpha}\)，其中 \(p\) 为奇质数。

证明不会。由此可以发现所有的质数都有原根。

原根判定定理

设 \(m \geq 3\) 且 \((a, m) = 1\)，则 \(a\) 是 \(m\) 的原根的充要条件是对于任意素数 \(p | \varphi(m)\)，均有 \(a^{\frac{\varphi (m)}{p}} \not \equiv 1 \pmod m\)。

证明：

充分性显然。

关于必要性，我们设 \(\delta_m(a)\) 为 \(a\) 模 \(m\) 的阶。

反证，若存在 \(a\) 满足 \(a^{\frac{\varphi(m)}{p}} \not \equiv 1 \pmod m\) 且 \(a\) 不为 \(m\) 的原根，那么 \(\delta_m(a) < \varphi(m)\) 且 \(\delta_m(a) | \varphi(m)\)。

故存在 \(\delta_m(a) | \frac{\varphi(m)}{p}\)，所以 \(a^{\frac{\varphi(m)}{p}} \equiv a^{\delta_m(a)} \equiv 1\)，矛盾。

模板

P11961 [GESP202503 五级] 原根判断

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
#define int long long
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 1000010;

int T, a, p;

inline int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1; a = a * a % p;
    }
    return res;
}

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

signed main() {
    T = read();
    while (T --) {
        a = read(), p = read();
        if (gcd(a, p) != 1) { puts("No"); continue; }
        bool flag = true;
        int phi = p - 1;
        for (int i = 2; i <= phi / i; i ++) 
            if (phi % i == 0) {
                if (qmi(a, (p - 1) / i, p) == 1) { flag = false; break; }
                while (phi % i == 0) phi /= i;
            }
        if (phi > 1) if (qmi(a, (p - 1) / phi, p) == 1) flag = false;
        if (flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

原根个数

\(m\) 的原根有可能不止一个。

先设 \(g\) 为 \(m\) 的一个原根，则 \(\forall 0 \leq i, j < \varphi(m)\)，\(g^i \not \equiv g^j \pmod m\)。

那么如果 \(g^k\) 是另一个原根，则要满足 \(g^0, g^k, ..., g^{(\varphi(m) - 1)k}\) 取遍 \(g^0 \sim g^{{\varphi(m) - 1}}\)。所以需要满足 \((k, \varphi(m)) = 1\)。

因此可以得到 \(m\) 的原根个数为 \(\varphi(\varphi(m))\)。

查找所有原根

\(m\) 的最小原根大概是 \(O(m^{0.25})\) 级别的，所以我们可以先找到最小的原根 \(g\)，然后根据原根个数部分，得到原根 \(g^k\)，其中 \((k, \varphi(m)) = 1\)。

模板

P6091 【模板】原根

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
#define int long long
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 1000010;
int primes[N], phi[N], cnt, st[N];
int n, d;

void eular() {
    int n = 1000000; phi[1] = 1;
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) primes[++ cnt] = i, phi[i] = i - 1;
        for (int j = 1; primes[j] <= n / i; j ++) {
            st[i * primes[j]] = true; 
            if (i % primes[j]) phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            else { phi[i * primes[j]] = phi[i] * primes[j]; break; }
        }
    }
}

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1; a = a * a % p;
    }
    return res;
}

bool check(int g) {
    if (gcd(g, n) != 1 || qmi(g, phi[n], n) != 1) return false;
    int ph = phi[n];
    for (int i = 2; i <= ph / i; i ++) 
        if (ph % i == 0) {
            if (qmi(g, phi[n] / i, n) == 1) return false;
            while (ph % i == 0) ph /= i;
        }
    if (ph > 1) if (qmi(g, phi[n] / ph, n) == 1) return false;
    return true;
}

void solve() {
    n = read(), d = read();

    int g = 0;
    for (int i = 1; i < n; i ++) 
        if (check(i)) { g = i; break; }
    if (!g) return puts("0\n"), void();
    
    vector<int> ans;
    for (int i = 0; i < phi[n]; i ++) 
        if (gcd(i, phi[n]) == 1) ans.push_back(i);
    for (int i = 0; i < ans.size(); i ++) ans[i] = qmi(g, ans[i], n);
    sort(ans.begin(), ans.end()); printf("%d\n", ans.size());
    for (int i = d; i <= ans.size(); i += d) printf("%d ", ans[i - 1]);
    puts(""); 
}

signed main() {
    int T = read(); eular();
    while (T --) solve();
    return 0;
}