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

前置知识

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

欧拉函数

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

欧拉函数有如下性质:

  1. 是积性函数,gcd(a,b)=1\forall \gcd(a, b) = 1,都有 φ(a,b)=φ(a)φ(b)\varphi(a, b) = \varphi(a) \varphi(b)

  2. n=dnφ(d)n = \sum_{d \mid n} \varphi(d)

  3. 如果 gcd(a,m)=1\gcd(a, m) = 1,则有 aφ(m)1(modm)^{\varphi(m)} \equiv 1 \pmod m

  4. 由容斥原理可知,φ(n)\varphi(n) 可以由公式:

n=i=1ω(n)piki,piPφ(n)=n×i=1npi1pin = \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}

得到,具体证明由性质 11 得出。

费马小定理

给定素数 pp,如果 apa \perp p,那么有 ap11(modp)a ^ {p - 1} \equiv 1 \pmod p

证明 给出链接。

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

aφ(p)1(modp),apa ^ {\varphi(p)} \equiv 1 \pmod p ,a \perp p

这个称作欧拉定理

定义

给定 aZ,mNa \in \mathbb{Z}, m \in \mathbb{N^*},由欧拉定理可知,若 ama \perp m,有 aφ(m)1(modm)a ^ {\varphi(m)} \equiv 1 \pmod m

因此必然存在一个最小的 nn 使得 an1(modm)a ^ n \equiv 1 \pmod m,我们将这个最小的 nn 称作 aamm 的阶,记作 δm(a):=n\delta_m(a) := n

在抽象代数中,它的本质aa 在模 mm​ 下生成的循环子群的最小数量

主要性质

它有大量很好的性质:

  • gcd(a,m)=1\gcd(a, m) = 1 下,必然存在 δm(a)\delta_m(a)

    有欧拉定理可知,它保证了 δm(a)\delta_m(a) 至少可以是 φ(m)\varphi(m)

  • a,a2,a3,,aδm(a)a,a^2,a^3,\dots,a^{\delta_m(a)} 在模 mm​ 意义下互不相同。

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

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

    假设存在 i,j(0<i<jδm(a))i,j(0 \lt i \lt j \le \delta_{m}(a)) 满足 aiaj(modm)a ^ i \equiv a ^ j \pmod m,那么说明存在 aaj1(modm)a ^ {|a - j|} \equiv 1 \pmod m0<ij<δm(a)0 \lt |i - j| \lt \delta_{m}(a),故假设不成立。

  • ama \perp mbmb \perp m 下,有:

    δm(ab)=δm(a)×δm(b)    δm(a)δm(b)\delta_m(ab) = \delta_m(a) \times \delta_m(b) \iff \delta_m(a) \perp \delta_m(b)

    给出 证明,感性可以用最小公倍数辅助理解。

  • ak1(modm)a ^ k \equiv 1 \pmod m,则 δm(a)k\delta_m(a) \mid k​。

    同样采取反证法,对 kk 做代余除法,则有:

    k=q×δm(a)+r,0r<δm(a)k = q \times \delta_m(a) + r, 0 \le r \lt \delta_m(a)

    若性质不成立,则 r0r \neq 0,有:

    arar×aq×δm(a)ak1(modm)a^r \equiv a^r \times a^{q \times \delta_m(a)} \equiv a^k \equiv 1 \pmod m

    因为 r<δm(a)r \lt \delta_m(a) 矛盾,因此性质成立。

原根

定义

gZ,mN,gmg \in \mathbb{Z}, m \in \mathbb{N^*},g \perp m,如果有 δm(g)=φ(m)\delta_m(g) = \varphi(m),我们称 gg 为模 mm​ 的原根。

重要性质

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

证明:根据阶的性质二,将 φ(m)\varphi(m) 带入 δm(g)\delta_m(g) 可以得到。

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

原根的存在和个数

原根存在定理:

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

证明不会,见 OI Wiki

原根个数:

对于一个数 mm,如果它存在原根,那么它的原根个数为 φ(φ(m))\varphi(\varphi(m))

mm 的一个原根为 gg,那么 g,g2,,gφ(m)g, g^2, \dots,g^{\varphi(m)} 包含了 mm 的所有原根,并且这些原根满足:

δm(gk)=φ(m)    kφ(m)\delta_m(g^k) = \varphi(m) \iff k \perp \varphi(m)

这样的 kkφ(φ(m))\varphi(\varphi(m)) 个,就是 mm 的原根个数。

判定原根定理

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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';
}

Reference

原根 - OI Wiki

欧拉函数 - OI Wiki

欧拉定理 & 费马小定理 - OI Wiki

原根 - 维基百科,自由的百科全书

P6091 【模板】原根 - 洛谷

题解 P6091 【模板】原根 - 洛谷专栏