本文是以 oi-wiki 为基础，自己手 $\LaTeX$ 整理的式子；和本博客、oi-wiki 原文一样遵循 CC BY-SA 4.0 协议。

---

阶

若 $a \perp m$，则将使 $a^l \equiv 1 \pmod m$ 成立的最小的 $l$ 称为 $a$ 关于 $m$ 的阶，记作 $\operatorname{ord}_m a$。

若 $\operatorname{ord}_m a = l$，则 $\operatorname{ord}_m a^t = \frac l{\gcd(t, l)}$。

由欧拉定理，设 $\operatorname{ord}_m a = l$，则 $a^n \equiv 1 \pmod m$ 当且仅当 $l \mid n$，即 $l \mid \varphi(m)$。

• 设 $p$ 是素数，$\operatorname{ord}_p a = l$，那么有且仅有 $\varphi(l)$ 个关于 $p$ 的阶为 $l$ 且模意义下不相等的数。

• 设 $\operatorname{ord}_m a = l$，则 $1, a, a^2, \cdots, a^{l - 1}$ 在模 $m$ 意义下互不相等。

• 设 $p$ 是素数，$l \mid p - 1$，则存在 $\varphi(l)$ 个关于 $p$ 的阶为 $l$ 且模意义下不相等的数。

• 若 $m = \prod_{i = 1}^k p_i^{a_i}$，则 $\operatorname{ord}_m a = \mathrm{lcm}_{i = 1}^k \{ \operatorname{ord}_{p_i}^{a_i} \}$。

原根

若 $g \perp m, \operatorname{ord}_m g = \varphi(m)$ 则称 $g$ 是 $m$ 的一个原根。

$g$ 为 $m$ 的原根当且仅当 $\{g, g^2, \cdots, g^{\varphi(m)} \}$ 构成 $m$ 的一个缩系。

原根的存在性

若 $m$ 有原根，则 $m$ 一定是下列形式：$2, 4, p^a, 2p^a$，其中 $p$ 是奇素数，$a$ 是正整数。

求所有原根

设 $g$ 为 $m$ 的一个原根，则集合 $S = \{g^s \mid 1 \le s \le \varphi(m), s \perp \varphi(m)\}$ 给出 $m$ 的所有原根。因此，若 $m$ 有原根，则 $m$ 有 $\varphi(\varphi(m))$ 个原根。

求一个原根

对 $p - 1$ 进行质因数分解得到不同的质因子 $d_1, d_2, \cdots, d_m$，对于任意的 $1 < a < p$，要判定 $a$ 是否是模 $p$ 的原根，只需要检验 $a^{(p - 1) / d_1}, a^{(p - 1) / d_2}, \cdots, a^{(p - 1) / d_m}$ 这 $m$ 个数中是否存在一个数在模 $p$ 意义下等于 $1$。若存在，则 $a$ 不是 $p$ 的原根；若不存在，则 $a$ 是 $p$ 的原根。

更形式化地，若 $g \perp m$，$p_1, p_2, \cdots, p_k$ 是 $\varphi(m)$ 的所有不同的质因数，则 $g$ 是 $m$ 的原根，当且仅当 $\forall 1 \le i \le k, g^{\varphi(m) / p_i} \not \equiv 1 \pmod m$。

---

洛谷模板题

problem

给定不超过 $N$ 的若干个数 $n$，求出它们所有的原根。

solution

按照上面的做法，先筛出 $\varphi(1 \dots n)$，对于每个 $n$ 暴力枚举最小的原根（是 $O \left( n^\frac 14 \right)$ 的），再递推求出所有原根即可。

code

using ll = long long;

std::bitset<1000003> v, ex;
int fp[11], p[78501], ans[1000003], phi[1000003];

void prework() {
  constexpr int N = 1'000'000;
  int M = 0;
  
  /* get phi[1..N] and M */
  
  ex.set(2), ex.set(4);
  for (int i = 2; i <= M; ++i)
    for (ll j = p[i]; j <= N; j *= p[i]) {
      ex.set(j);
      if (j <= 500'000) ex.set(j << 1);
    }
}

int Pow(ll b, ll p, ll m);

bool check(int g, int p, int K) {
  if (Pow(g, phi[p], p) != 1) return 0;
  for (int i = 1; i <= K; ++i)
    if (Pow(g, phi[p] / fp[i], p) == 1) return 0;
  return 1;
}

int solve(int p) {
  int q = phi[p], len = 0, K = 0, mn = 1;
  for (int i = 2; i * i <= q; ++i)
    if (q % i == 0) {
      fp[++K] = i;
      do q /= i; while (q % i == 0);
    }
  if (q > 1) fp[++K] = q;

  while (mn < p && !check(mn, p, K)) ++mn;

  for (int i = 1, s = mn; i <= phi[p]; ++i, s = 1ll * s * mn % p)
    if (std::__gcd(i, phi[p]) == 1)
      ans[++len] = s;
  return len;
}