【笔记/模板】阶和原根

原本应该放在同与代数里面讲的，但是我还没有系统地学过，因此单独说一下。

前置知识

前置知识不多，只要涉及费马小定理和欧拉函数。

欧拉函数

欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 的与 $n$ 互质的数的个数。特别的，素数的欧拉函数 $\varphi(p) = p - 1$ 。

欧拉函数有如下性质：

是积性函数， $\forall \gcd(a, b) = 1$ ，都有 $\varphi(a, b) = \varphi(a) \varphi(b)$
$n = \sum_{d \mid n} \varphi(d)$
如果 $\gcd(a, m) = 1$ ，则有 a $^{\varphi(m)} \equiv 1 \pmod m$
由容斥原理可知， $\varphi(n)$ 可以由公式：

$n = \prod_{i = 1}^{\omega (n)} p_i^{k_i},\forall p_i \in \mathbb{P} \\ \varphi(n) = n \times \prod_{i = 1}^n \frac{p_i - 1}{p_i}$

得到，具体证明由性质 $1$ 得出。

费马小定理

给定素数 $p$ ，如果 $a \perp p$ ，那么有 $a ^ {p - 1} \equiv 1 \pmod p$ 。

证明给出链接。

费马小定理可以和欧拉函数的性质相结合，得到：

$a ^ {\varphi(p)} \equiv 1 \pmod p ,a \perp p$

这个称作欧拉定理。

阶

定义

给定 $a \in \mathbb{Z}, m \in \mathbb{N^*}$ ，由欧拉定理可知，若 $a \perp m$ ，有 $a ^ {\varphi(m)} \equiv 1 \pmod m$ 。

因此必然存在一个最小的 $n$ 使得 $a ^ n \equiv 1 \pmod m$ ，我们将这个最小的 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a) := n$ 。

在抽象代数中，它的本质是 $a$ 在模 $m$ 下生成的循环子群的最小数量。

主要性质

它有大量很好的性质：

在 $\gcd(a, m) = 1$ 下，必然存在 $\delta_m(a)$ 。

有欧拉定理可知，它保证了 $\delta_m(a)$ 至少可以是 $\varphi(m)$ 。
$a,a^2,a^3,\dots,a^{\delta_m(a)}$ 在模 $m$ 意义下互不相同。

结合这个你大致就明白抽象代数中阶的本质是什么了。

比较显然，反证法可以证明。

假设存在 $i,j(0 \lt i \lt j \le \delta_{m}(a))$ 满足 $a ^ i \equiv a ^ j \pmod m$ ，那么说明存在 $a ^ {|a - j|} \equiv 1 \pmod m$ 而 $0 \lt |i - j| \lt \delta_{m}(a)$ ，故假设不成立。
在 $a \perp m$ 和 $b \perp m$ 下，有：

$\delta_m(ab) = \delta_m(a) \times \delta_m(b) \iff \delta_m(a) \perp \delta_m(b)$

给出证明，感性可以用最小公倍数辅助理解。
若 $a ^ k \equiv 1 \pmod m$ ，则 $\delta_m(a) \mid k$ 。

同样采取反证法，对 $k$ 做代余除法，则有：

$k = q \times \delta_m(a) + r, 0 \le r \lt \delta_m(a)$

若性质不成立，则 $r \neq 0$ ，有：

$a^r \equiv a^r \times a^{q \times \delta_m(a)} \equiv a^k \equiv 1 \pmod m$

因为 $r \lt \delta_m(a)$ 矛盾，因此性质成立。

原根

定义

设 $g \in \mathbb{Z}, m \in \mathbb{N^*},g \perp m$ ，如果有 $\delta_m(g) = \varphi(m)$ ，我们称 $g$ 为模 $m$ 的原根。

重要性质

若一个数 $m$ 有原根 $g$ ，那么 $g,g^1,g^2,\dots,g^{\varphi(m)}$ 构成模 $m$ 的简化剩余系。

证明：根据阶的性质二，将 $\varphi(m)$ 带入 $\delta_m(g)$ 可以得到。

特别地，如果 $m$ 是素数，则这 $\varphi(m)$ 个数在模 $m$ 意义下互不相同并且与 $m$ 互质，通过欧拉定理可以得出。因此如果存在原根，那么它的幂次会遍历所有简化剩余系中的元素。

原根的存在和个数

原根存在定理：

一个数 $m$ 存在原根当且仅当 $m = 2, 4, p ^ k, 2p ^ k,(p \in \mathbb{P}, k \in \mathbb{Z}, 2 \nmid p)$ 。

证明不会，见 OI Wiki。

原根个数：

对于一个数 $m$ ，如果它存在原根，那么它的原根个数为 $\varphi(\varphi(m))$ 。

设 $m$ 的一个原根为 $g$ ，那么 $g, g^2, \dots,g^{\varphi(m)}$ 包含了 $m$ 的所有原根，并且这些原根满足：

$\delta_m(g^k) = \varphi(m) \iff k \perp \varphi(m)$

这样的 $k$ 有 $\varphi(\varphi(m))$ 个，就是 $m$ 的原根个数。

判定原根定理

在前面讲的阶的性质四中，如果 $a ^ k \equiv 1 \pmod m$ ，那么 $\delta_m(a) \mid k$ ，又因为原根要求 $\delta_m(a) = \varphi(m)$ 。因此我们找到每一个 $\varphi(m)$ 的质因子 $d_1,d_2,\dots,d_t$ 即可，如果存在 $d_k$ 满足 $a ^{\frac{\varphi(m)}{d_k}} \equiv 1 \pmod m$ ，则说明 $a$ 不是 $m$ 的原根，它的阶小于 $\varphi(m)$ 。否则 $a$ 为 $m$ 的原根。

那么如何枚举 $a$ 呢？答案是暴力。目前被证明了的其中一个存在原根的数 $m$ 的最小原根上界为 $m^{\frac{1}{4} + \epsilon}$ ，可以看见这是非常小的，因此我们考虑暴力的方式，从而得到一个数的最小原根，并推出其它的所有原根。

以 P6091 【模板】原根 - 洛谷为例：

inline void Init()
{
    phi[1] = 1;
    for (int i = 2; i < N; i ++)
    {
        if (!vis[i]) primes[++ cnt] = i, phi[i] = i - 1;
        for (int j = 1; i * primes[j] < N; j ++) 
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }

    rt[2] = rt[4] = true;    // 依据原根的存在原理
    for (int i = 2; i <= cnt; i ++)
    {
        for (int j = 1; primes[i] * j < N; j *= primes[i]) rt[j * primes[i]] = true;
        for (int j = 2; primes[i] * j < N; j *= primes[i]) rt[j * primes[i]] = true; 
    }
}

int n, d;
int divs[N], tot;

inline void divide(int x)
{
    tot = 0;
    for (int i = 2; i <= x / i; i ++)
        if (x % i == 0)
        {
            divs[++ tot] = i;
            while (x / i == 0) x /= i;
        }
    if (x > 1) divs[++ tot] = x;
}

inline int ksm(int base, int k, int mod)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * base % mod;
        base = base * base % mod, k >>= 1;
    }
    return res;
}

inline bool check(int cur, int p)    // 依据原根判定定理
{
    if (ksm(cur, phi[p], p) != 1) return false;
    for (int i = 1; i <= tot; i ++)
        if (ksm(cur, phi[p] / divs[i], p) == 1) return false;
    return true;
}

inline int find(int p)    // 找到 p 的最小原根
{
    for (int cur = 1; cur < p; cur ++)
        if (check(cur, p)) return cur;
    return 0;
}

void solve()
{
    read(n, d);
    if (!rt[n]) return void(puts("0\n"));

    divide(phi[n]);
    int minrt = find(n);

    vector<int> ans;
    for (int cur = 1, prod = 1; cur <= phi[n]; cur ++)    // 所有其他原根都是最小原根的若干幂
    {
        prod = prod * minrt % n;
        if (__gcd(cur, phi[n]) == 1) ans.emplace_back(prod);
    }
    sort(begin(ans), end(ans));
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i ++)
        if ((i + 1) % d == 0) cout << ans[i] << ' ';
    cout << '\n';
}