原根与指数

阶数与原根

根据欧拉定理，当 $m > 1, (a, m) = 1$ 时，$a^{\phi(m)} \equiv 1 \pmod m$，因此在 $a$ 的正方幂 $a, a^2, a^3, \cdots$ 中，必有正整数 $t$ 存在，使得 $a^t \equiv 1 \pmod m$。于是我们给出

定义1：设 $m > 1, (a, m) = 1, t$ 是使 $a^t \equiv 1 \pmod m$ 成立的最小正整数，则称 $t$ 为 $a$ 关于模 $m$ 的阶数(或阶)

由定义可知 $t \le \phi(m)$

定义2: 若 $a$ 关于模 $m$ 的阶数是 $\phi(m)$，则称 $a$ 为 $m$ 的一个原根

$m$ 可能有多个原根

定理1: 设 $a$ 关于模 $m$ 的阶数为 $t$，则 $1 = a^0, a_1, \cdots, a^{t - 1}$ 关于模 $m$ 两两不同余
证：假设有两个整数 $i, j$，满足条件 $a^i \equiv a_j \pmod m(0 \le j < i \le t - 1)$
因 $(a, m) = 1$，则有 $a^{i - j} \equiv 1 \pmod m(0 < i - j \le t - 1)$
这与 $t$ 是 $a$ 关于模 $m$ 的阶矛盾

推论：设 $(g, m) = 1$，则 $g$ 是模 $m$ 的一个原根的充要条件是 $1, g, g^2, \cdots, g^{\phi(m) - 1}$ 构成模 $m$ 的一个缩系
证：设 $g$ 是模 $m$ 的原根，则 $(g, m) = 1$，由定理 $1$ 知，$1, g, g^2, \cdots, g^{\phi(m) - 1}$ 中任意两个数关于模 $m$ 不同余，且 $(g^k, m)(k = 0, 1, \cdots, \phi(m) - 1)$，因此，它们构成模 $m$ 的一个缩系
反之，设 $1, g, g^2, \cdots, g^{\phi(m) - 1}$ 构成模 $m$ 的缩系，则当 $0 < k < \phi(m)$ 时，$g^k \not \equiv m$，又 $g^{\phi(m)} \equiv 1 \pmod m$，即 $g$ 关于模 $m$ 的阶是 $\phi(m)$，所以 $g$ 是模 $m$ 的原根

定理2: 设 $a$ 关于模 $m$ 的阶是 $t$，则 $a^r \equiv a^s \pmod m$ 的充要条件是 $r \equiv s \pmod t$

证：根据带余除法，设 $r = q_1 t + r_1(0 \le r_1 < t), s = q_t t + s_1(0 \le s_1 < t)$ 则 $a^r = (a^t)^{q_1} \cdot a^{r_1} \equiv a^{r_1} \pmod m, a^s = (a^t)^{q_2} \cdot a^{s_1} \equiv a^{s_1} \pmod m$

于是 $a^r \equiv a^s \pmod m \Leftrightarrow a^{r_1} \equiv a^{s_1} \pmod m \Leftrightarrow r_1 = s_1 \Leftrightarrow r \equiv s \pmod t$

推论1: 设 $a$ 关于模 $m$ 的阶是 $t$，则 $a^r \equiv 1 \pmod m$ 成立的充要条件是 $t \mid r$
证：令定理 $2$ 中的 $s = 0$ 即得

推论2: 设 $a$ 关于模 $m$ 的阶是 $t$，则 $t \mid \phi(m)$
证：由推论 $1$ 可得

原根存在的条件

不存在原根的情形

关于模 $m$ 的原根并不总是存在的。例如, $m = 8$ 时，$\phi(8) = 4$，而与 $8$ 互素的数是全体奇数，又任意奇数的平方关于模 $8$ 都与 $1$ 同余，因此 $8$ 的原根是不存在的

一般地，我们有如下定理：

定理1: 设 $m = 2^k p_1^{k_1} \cdots p_r^{k_r}$，这里 $k \ge 0, k_i \ge 1, p_1, p_2, \cdots, p_r$ 是不同的奇素数，则：
(1) 当 $k = 2$ 且 $m \not = 4$ 时，模 $m$ 没有原根
(2) 当 $k > 2$ 时，模 $m$ 没有原根
(3) 当 $r \ge 2$ 时，模 $m$ 没有原根

存在原根的情形

定理：设 $m > 2$，$\phi(m)$ 的所有不同的素因数是 $q_1, q_2, \cdots, q_s, (g, m) = 1$，则 $g$ 是 $m$ 的一个原根的充要条件是

$$g^{\frac{\phi(m)}{q_i}} \not \equiv 1 \pmod m (i = 1, 2, \cdots, s)$$

定理：对于每个奇素数，模 $p$ 的原根一定存在

计算原根的方法

模为奇素数 p 的原根的求法

方法1: 设 $p$ 为奇素数，$\phi(p)$ 的所有不同的素因数是 $q_1, q_2, \cdots, q_s$。若 $(g, p) = 1$ 且 $g^{\frac{p - 1}{q_i}} \not \equiv 1 \pmod p (i = 1, 2, \cdots, s)$，则 $g$ 是模 $p$ 的一个原根

51Nod 1135 原根

#include <cstdio>
int p, cnt;
int prime[20];
long long my_pow(int x, int y) {
    long long ret = 1, t = x;
    while (y) {
        if (y & 1) { ret = ret * t % p; }
        y >>= 1; t = t * t % p;
    }
    return ret;
}
int main() {
    scanf("%d", &p);
    int t = p - 1;
    for (int i = 2; i * i <= t; ++i) {
        if (t % i == 0) { prime[cnt++] = i; t /= i; }
        while (t % i == 0) { t /= i; }
    }
    if (t != 1) { prime[cnt++] = t; }
    for (int i = 2; ; i++) {
        bool flag = true;
        for (int j = 0; j < cnt; ++j) {
            if (my_pow(i, (p - 1) / prime[j]) == 1ll) {
                flag = false; break;
            }
        }
        if (flag) { printf("%d\n", i); break; }
    }
    return 0;
}