一、最大公约数
定义
不全为 \(0\) 的整数 \(a, b\) 的最大公约数是指能够同时整除 \(a\) 和 \(b\) 的最大整数。
欧几里得算法(gcd)
gcd是用来求解两个整数的最大公约数
定理1.2.1
对于整数 \(a, b, m, n\)，若 \(c \mid a，c \mid b\)，则 \(c \mid (ma + nb)\)
证：\(\because c \mid a，c \mid b\)
设 \(a = ce，b = cf\)
\(\therefore ma + nb = mce + ncf = c(me + nf)\)
\(\therefore c \mid (ma + nb)\)
定理1.2.2
若 \(a, b, c\) 是整数，则 \(\gcd(a + cb, b) = \gcd(a, b)\)
证：设 \(\gcd(a, b) = d\)，根据定理1.2.1，\(d \mid (a + cb)\)
\(\therefore d\) 是 \(a + cb\) 和 \(b\) 的公约数。
\(\therefore a\) 和 \(b\) 的公约数与 \((a + cb)\) 和 \(b\) 的公约数一一对应。
\(\therefore \gcd(a, b) = \gcd(a + cb, b)\)
反过来，设 \(\gcd(a + cb, b) = e\)，根据定理1.2.1，\(e \mid [(a + cb) - cb] = a\)
\(\therefore e\) 是 \(a\) 和 \(b\) 的公约数。
\(\therefore (a + cb)\) 和 \(b\) 的公约数与 \(a\) 和 \(b\) 的公约数一一对应。
\(\therefore \gcd(a + cb, b) = \gcd(a, b)\)
解法
令整数 \(r_0 = a\)，\(r_1 = b\) 满足 \(a \geq b > 0\)，如果连续做带余除法得到 \(r_j = r_{j + 1}q_{j + 1} + r_{j + 2}\)，且 \(r_{j + 2} = 0\)，那么 \(\gcd(a, b) = r_{j + 1}\)
正确性证明：通过连续的带余除法可以得到：
\[r_0 = r_1q_1 + r_2\\ r_1 = r_2q_2 + r_3\\ \vdots\\ r_j = r_{j + 1}q_{j + 1} + r_{j + 2}\\ \vdots\\ r_{n - 2} = r_{n - 1}q_{n - 1} + r_n\\ r_{n - 1} = r_nq_n \]根据定理1.2.2，\(\gcd(a, b) = \gcd(r_0, r_1) = \gcd(r_1, r_2) = \dots = (r_{n - 1}, r_n) = (r_n, 0)\)，因此 \(\gcd(a, b) = r_n\)
裴蜀定理
定理1.3.1
对于两个不全为 \(0\) 的整数，\(\gcd(a, b)\) 是 \(a, b\) 的线性组合中最小的一个。
证：设 \(d\) 为 \(a, b\) 的线性组合中最小的一个，设 \(d = ma + nb\)，\(a = dq + r(0 \leq r < d)\)
\(\therefore r = a - dq = a - q(ma + nb) = (1 - qm)a - qnb\)
\(\therefore r\) 也是 \(a, b\) 的线性组合。
\(\because 0 \leq r < d\) 且 \(d\) 为 \(a, b\) 的线性组合中最小的一个。
\(\therefore r = 0\)
\(\therefore d \mid a\)，同理可得 \(d \mid b\)
假设 \(a, b\) 还有公因数 \(c\)
\(\therefore c \mid a, c \mid b\)
\(\therefore c \mid ma + nb = d\)
\(\therefore d \geq c\)
\(\therefore d\) 是 \(a, b\) 的最大公约数。
\(\therefore \gcd(a, b)\) 是 \(a, b\) 的线性组合中最小的一个。
内容
裴蜀定理是用来判断一个形如 \(ax + by = c\) 是否有整数解。
对于整数 \(a, b\)，设 \(\gcd(a, b) = d\)，如果 \(d \nmid c\)，那么方程 \(ax + by = c\) 没有整数解，如果 \(d \mid c\)，那么方程有无数多组形如 \(x = x_0 + (b / d)n\)，\(y = y_0 - (a / d)n\) 的整数解
证：若整数 \(x, y\) 满足 \(ax + by = c\)
\(\because d \mid a, d \mid b\)
\(\therefore\) 根据定理1.2.1，有 \(d \mid (ax + by) = c\)
\(\therefore\) 如果 \(d \nmid c\)，那么原方程无解
假设 \(d \mid c\)，根据定理1.3.1，存在整数 \(s, t\) 满足 \(d = as + bt\)
设 \(c = de\)，那么 \(c = de = (as + bt)e = a(se) + b(te)\)
\(\therefore x_0 = se, y_0 = te\) 就是原方程的一组特解。
令 \(x = x_0 + (b / d)n, y = y_0 - (a / d)n\)
\(\therefore ax + by = ax_0 + a(b / d)n + by_0 - b(a / d)n = ax_0 + by_0 = c\)
\(\therefore x = x_0 + (b / d)n, y = y_0 - (a / d)n\) 是原方程的通解。
反过来，假设整数 \(x, y\) 满足 \(ax + by\) = c
\(\because ax_0 + by_0 = c\)
\(\therefore (ax + by) - (ax_0 + by_0) = 0\)
\(\therefore a(x - x_0) - b(y - y_0) = 0\)
\(\therefore a(x - x_0) = b(y_0 - y)\)
\(\therefore (a / d)(x - x_0) = (b / d)(y_0 - y)\)
\(\because \gcd(a, b) = d\)
\(\therefore \gcd(a / d, b / d) = 1\)
\(\therefore\) 根据可除性前置一(见同余/同余的性质/可除性)，\((a / d) \mid (y_0 - y)\)
\(\therefore n(a / d) = y_0 - y\)
\(\therefore y = y_0 - (a / d)n\)，将这个 \(y\) 值代入原方程得：
\(a(x - x_0) = b(a / d)n\)
\(x = x_0 + (b / d)n\)
扩展欧几里得算法(exgcd)
求 \(ax + by = gcd(a, b)\) 的特解关键在于递归的思想
现在已知 \(\gcd(a, b) = \gcd(b, a \bmod b)\)
因此 \(ax + by = bx' + (a \bmod b)y' = bx' + (a - b \times \lfloor\frac{a}{b}\rfloor)y' = ay' + b(x' - \lfloor\frac{a}{b}\rfloor y')\)
\(\therefore x = y', y = x' - \lfloor\frac{a}{b}\rfloor y'\)
先一层层递归，回溯时求解原方程的解。
exgcd代码：
int extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;//递归边界
return 0;
}
int d = extend_gcd(b, a % b, y, x);//递归
y -= a / b * x;//回溯
return d;
}
二、素数
定义
素数是大于 \(1\) 的正整数，并且除了 \(1\) 和它本身外不能被其他正整数所整除，素数又被称作质数。
大于 \(1\) 的不是素数的正整数称为合数。
筛法求素数
下面给出两种可以在线性时间内筛出 \(1\) 到 \(n\) 之间的素数的方法。
埃拉托色尼斯筛法
首先，一个正整数的倍数一定是合数。
如果一个数是合数，那他一定能表示成比他小的数的倍数。
我们考虑用已经筛出的素数的倍数表示合数。
从 \(2\) 开始，如果这个数没有被标记过，那么将这个数标记为素数，他的倍数都标记为合数。
这个方法被称作埃拉托色尼斯筛法，简称埃氏筛，复杂度 \(O(n \log \log n)\)
复杂度证明：设 \(\pi(n)\) 表示小于等于 \(n\) 的素数个数，\(p_k\) 表示这 \(\pi(n)\) 个数中第 \(k\) 小的数。
在 \(1\) 到 \(n\) 的数中，一个素数最多会筛出 \(\displaystyle\frac{n}{p_k}\) 个合数，因此总复杂度为 \(O(\displaystyle\sum_{k=1}^{\pi(n)}\frac{n}{p_k}) = O(n \sum_{k=1}^{\pi(n)}\frac{1}{p_k})\)
设 \(n\) 的唯一分解是 \(\displaystyle\prod_{i=1}^m p_i^{c_i}\)
记 \(\omega(n)\) 表示 \(n\) 本质不同的质因子个数，即 \(\displaystyle\sum_{p \in \mathbb{P}, p \leq n} [p \mid n]\)
记 \(d(n)\) 表示 \(n\) 的因数个数，即 \(\displaystyle\sum_{d \leq n} [d \mid n]\)，从唯一分解的角度考虑，枚举每个素数的个数，那么有 \(d(n) = \displaystyle\prod_{i=1}^m(c_i + 1)\)
\(\therefore n \displaystyle\sum_{k=1}^{\pi(n)}\frac{1}{p_k} = n \sum_{i=1}^n \omega(i)\)
\(\because 2^{\omega(n)}\) 表示每个素数只有选或不选两种状态下 \(n\) 的因子个数，而 \(d(i)\) 则表示每个素数可以选 \([0, c_i]\) 次的因子个数。
\(\therefore \displaystyle\sum_{i=1}^n 2^{\omega(i)} \leq \sum_{i=1}^n d(i)\)
\(\because\) 将一个数唯一分解的复杂度是 \(O(\log n)\)
\(\therefore \displaystyle\sum_{i=1}^n 2^{\omega(i)} \leq O(n \log n)\)
中置知识：下凸函数
如果一个函数 \(f(x)\) 的一阶导单调递增，二阶导单调不下降，那么这个函数就是一个下凸函数，可以看作 \(f(x)\) 在增加，他的斜率也在增加，如图：
就是一个下凸函数。
设 \(f(x) = n^x(n ＞ 1)\)
\(\therefore f'(x) = n^x \text{ ln } x\)，\(f^{(2)}(x) = n^x \text{ ln } n + \displaystyle\frac 1x\)，发现这两个函数均为增函数。
\(\therefore f(x) = n^x\) 是下凸函数。
中置知识：琴生不等式
一般形式：若 \(f(x)\) 是下凸函数，则对于任何取值的 \(x_1, x_2, x_3, \dots , x_n\)，都有
\[\displaystyle\frac{\displaystyle\sum_{i=1}^nf(x_i)}{n} \geq f(\frac{\displaystyle\sum_{i=1}^{n}x_i}{n}) \]加权形式：若 \(f(x)\) 是下凸函数，\(a_1, a_2, a_3, \dots , a_n\) 是正数且 \(\displaystyle\sum_{i=1}^na_i\)，则对于任何取值的 \(x_1, x_2, x_3, \dots , x_n\)，都有
\[\displaystyle\sum_{i=1}^na_if(x_i) \geq f(\sum_{i=1}^{n}a_ix_i) \]证：(加权形式)
考虑数学归纳法
当 \(n = 1\) 时第一个式子是线性增加的，而第二个式子是非线性增加的，又因为 \(f(x)\) 是下凸函数，它的增长比线性快，又因为 \(a_i \leq 1\)，乘 \(a_i\) 后两式子减小，第一个减小得更慢，结论显然成立。
当 \(n ＞ 1\) 时，\(f(\displaystyle \sum_{i=1}^na_ix_i) = f((1 - a_n)(\frac{\displaystyle \sum_{i=1}^{n - 1}a_ix_i}{1 - a_{n - 1}}) + a_nx_n) \leq (1 - a_n)f(\sum_{i=1}^{n - 1}a_ix_i) + a_nf(x_n) \leq \displaystyle\sum_{i=1}^na_if(x_i)\)
不等式成立。
\(\because f(x) = 2^x\) 是下凸函数。
\(\therefore \displaystyle\sum_{i=1}^n 2^{\omega(i)} \geq n2^{\frac{\sum_{i=1}{n}\omega(i)}{n}}\)
\(\therefore n2^{\frac{\sum_{i=1}^{n}\omega(i)}{n}} \leq O(\log n)\)
\(\therefore \displaystyle\frac{\displaystyle\sum_{i=1}^{n}\omega(i)}{n} \leq O(\log \log n)\)
\(\therefore \displaystyle\sum_{i=1}^{n}\omega(i) \leq O(\log \log n)\)
\(\therefore\) 埃氏筛的时间复杂度是 \(O(n \log \log n)\)
完整代码：P3383 【模板】线性筛素数
#include<bits/stdc++.h>
using namespace std;
const int PP = 1e8 + 9;
int prime[PP], p_cnt;
bool isPrime[PP];
void getPrime(int n){
for(int i = 2; i < n; ++i)
isPrime[i] = true;
for(int i = 2; i < n; ++i){
if(isPrime[i]){//一个数没被标记过
prime[++p_cnt] = i;//记录素数
if(1ll * i * i < n)//防止越界
for(int j = i * i; j <= n; j += i)//根据合数i的最小质因子小于等于sqrt(i)，可以从i*i开始筛，优化常数
isPrime[j] = false;//他的倍数标记为合数
}
}
}
signed main(){
int n, q;
scanf("%d%d", &n, &q);
getPrime(n);
while(q--){
int x;
scanf("%d", &x);
printf("%d\n", prime[x]);
}
return 0;
}
欧拉筛法
埃氏筛十分优秀，但每个数会被它的所有质因子都筛一遍，而使用欧拉筛可以使每个数只被它的最小质因子筛一遍，时间复杂度可以达到 \(O(n)\)
每找到一个没被标记的数，就将它记为素数，无论他是不是素数，都将它与已求出的素数相乘并将他标记为合数。
当遇到一个素数能整除当前的数，证明当前的数已经被这个素数标记过了，他乘其它质数也已经被这个质数标记了，就可以退出循环了。
完整代码：P3383 【模板】线性筛素数
#include<bits/stdc++.h>
using namespace std;
const int PP = 1e8 + 9;
int prime[PP], p_cnt;
bool isPrime[PP];
void getPrime(int n){
for(int i = 2; i < n; ++i)
isPrime[i] = true;
for(int i = 2; i < n; ++i){
if(isPrime[i])
prime[++p_cnt] = i;
for(int j = 1; j <= p_cnt && i * prime[j] < n; ++j){
isPrime[i * prime[j]] = false;//将prime[j]的第i倍标记为合数
if(i % prime[j] == 0)//因为prime数组从小到大排列，因此prime[j]一定是i的最小质因子，i乘其它质数一定会被prime[j]先筛掉，因此不用往后再筛了
break;
}
}
}
signed main(){
int n, q;
scanf("%d%d", &n, &q);
getPrime(n);
while(q--){
int x;
scanf("%d", &x);
printf("%d\n", prime[x]);
}
return 0;
}
欧拉函数
前置知识：积性函数
若对于任意正整数 \(a, b\)，\(\gcd(a, b) = 1\)，都有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 为积性函数。
若对于任意正整数 \(a, b\)，都有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 为完全积性函数。
定义
欧拉函数 \(\varphi(n)\) 表示不超过 \(n\) 且与 \(n\) 互质的数的个数，这 \(\varphi(n)\) 个数组成的集合也构成了 \(n\) 的既约剩余系。
欧拉函数的性质
1.若 \(p\) 是素数，则 \(\varphi(p) = p - 1\)；反过来，若 \(\varphi(p) = p - 1\)，则 \(p\) 是素数。
证：若 \(p\) 是素数，那么任意小于 \(p\) 的素数都与 \(p\) 互质。因为有 \(p - 1\) 个这样的正整数，所以 \(\varphi(p) = p - 1\)
反过来，如果 \(p\) 不是素数，那么 \(p = 1\) 或 \(p\) 是合数。若 \(p = 1\)，那么 \(\varphi(1) = 1 \neq 0\)。若 \(p\) 是合数，那么一定存在正整数 \(d\) 使得 \(1 < d < p\) 且 \(d \mid p\)，显然 \(p\) 和 \(d\) 不互质，这说明 \(1\) 到 \(p - 1\) 至少有一个数与 \(p\) 不互质，则 \(\varphi(p) \leq n - 2\)。因此，如果 \(\varphi(p) = p - 1\)，那么 \(p\) 是素数。
2.对于素数 \(p\)，正整数 \(a\)，\(\varphi(p^a) = p^a - p^{a - 1}\)
证：不超过 \(p^a\) 且与 \(p^a\) 不互质的数就是那些不超过 \(p^a\) 且能被 \(p\) 整除的数：\(p, 2p, 3p, \dots, (p - 1)p, p^2, 2p^2, 3p^3 \dots (p - 1)p^{a - 1}, p^a\)，一共有 \(p^{a - 1}\) 个，所以有 \(p^a - p^{a - 1}\) 个不超过 \(p\) 数与 \(p\) 互质，因此 \(\varphi(p^a) = p^a - p^{a - 1}\)
3.(积性函数) 对于任意正整数 \(a, b\)，若 \(\gcd(a, b) = 1\)，那么 \(\varphi(ab) = \varphi(a)\varphi(b)\)
证：用下列方式列出不超过 \(ab\) 的正整数：
\[\begin{bmatrix} 1 & m + 1 & 2m + 1 & \dots & (n - 1)m + 1\\ 2 & m + 2 & 2m + 2 & \dots & (n - 1)m + 2\\ 3 & m + 3 & 2m + 3 & \dots & (n - 1)m + 3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ r & m + r & 2m + r & \dots & (n - 1)m + r\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ m & 2m & 3m & \dots & nm \end{bmatrix} \]假设 \(r\) 是不超过 \(m\) 的正整数且 \(\gcd(r, m) = d \neq 1\)，那么第 \(r\) 行的数都可以写成 \(km + r\) 形式
\(\because d \mid m\) 且 \(d \mid r\)
\(\therefore\) 根据定理1.2.1，\(d \mid (km + r)\)
\(\therefore r\) 行的所有数都与 \(mn\) 不互质。
\(\therefore\) 我们现在只用考虑 \(\gcd(m, r) = 1\) 的这 \(\varphi(m)\) 行的数，这第 \(r\) 行的数分别是 \(r, m + r, 2m + r, \dots, (n - 1)m + r\)
\(\because \gcd(r, m) = 1\)
\(\therefore\) 第 \(r\) 行的每个数都与 \(m\) 互质，可以发现，第 \(r\) 行所有数构成了模 \(n\) 的完全剩余系，所以恰好有 \(\varphi(n)\) 个数与 \(n\) 互质，它们又与 \(n\) 互质，因此它们与 \(mn\) 互质。
\(\because\) 这 \(\varphi(m)\) 行每行都有 \(\varphi(n)\) 个数与 \(mn\) 互质。
\(\therefore \varphi(mn) = \varphi(m)\varphi(n)\)
4.(通项公式) 设 \(n\) 的唯一分解是 \(\displaystyle\prod_{i=1}^m p_i^{c_i}\)，那么 \(\varphi(n) = n\displaystyle\prod_{i=1}^m(1 - \frac{1}{p_i})\)
证：根据性质3，\(\varphi\) 是积性函数。
\(\therefore \varphi(n) = \displaystyle\prod_{i=1}^m\varphi(p_i^{c_i})\)
根据性质2，\(\varphi(p_i^{c_i}) = p_i^{c_i} - p_i^{c_i - 1} = p_i^{c_i}(1 - \displaystyle\frac{1}{p_i})\)
\(\therefore \displaystyle\prod_{i=1}^m\varphi(p_i^{c_i}) = \prod_{i=1}^mp_i^{c_i}(1 - \frac{1}{p_i}) = \prod_{i=1}^mp_i^{c_i} \prod_{j=1}^m(1 - \frac{1}{p_j}) = n\prod_{i=1}^m(1 - \frac{1}{p_i})\)
5.(欧拉反演) 若 \(n\) 为正整数，则 \(\displaystyle\sum_{d \mid n}\varphi(d) = n\)
证：将 \(1\) 到 \(n\) 的整数构成的集合进行分类，如果整数 \(m\) 与 \(n\) 的最大公因数为 \(d\)，那么 \(m\) 属于 \(C_d\) 集合。
\(\therefore \gcd(m / d, n / d) = 1\)
\(\therefore C_d\) 集合中所包含整数个数就是所有不超过 \(n / d\) 且与 \(n / d\) 互质的数的个数。
\(\therefore C_d\) 集合中所包含整数个数就是 \(\varphi(n / d)\)
现在我们将 \(1\) 到 \(n\) 之间的整数划分成了若干个不相交的集合，且每个数只存在在一个集合中所以这些不同的集合所含整数的个数和就是 \(n\)
\(\therefore n = \displaystyle\sum_{d \mid n}\varphi(n / d)\)
因为 \(d\) 遍历了所有 \(n\) 的因子，\(n / d\) 也便利了所有 \(n\) 的因子。
\(\therefore n = \displaystyle\sum_{d \mid n}\varphi(n / d) = \displaystyle\sum_{d \mid n}\varphi(d)\)
6.若 \(a \mid b\)，则 \(\varphi(ab) = a \times \varphi(b)\)
证：\(\because a \mid b\)
\(\therefore a\) 对通项公式中 \(\displaystyle\prod_{i=1}^m(1 - \frac{1}{p_i})\) 部分没有影响，因为 \(a\) 只改变了 \(c_i\)，没改变 \(p_i\)
\(\because a\) 的加入让前半部分 \(n\) 变大了 \(a\) 倍。
\(\therefore \varphi(ab) = a \times \varphi(b)\)
线性筛欧拉函数
首先，对于一个素数 \(p\)，\(\varphi(p) = p - 1\)
利用欧拉筛
-
如果 \(prime[j] \mid i\)，根据性质6，有 \(\varphi(i \times prime[j]) = \varphi(i) \times prime[j]\)
-
如果 \(prime[j] \nmid i\)，因为 \(\prime[j]\) 为素数，因此 \(gcd(prime[j], i) = 1\)，根据性质3，有 \(\varphi(i \times prime[j]) = \varphi(i) \times \varphi(prime[j])\)
线筛代码：
const int N = 4e6 + 9;
int vis[N], prime[N], phi[N], sum[N], n;
void get_phi(){
phi[1] = 1;
int cnt = 0;
for(int i = 2; i < N; i++){
if(!vis[i]){
vis[i] = i;
prime[cnt++] = i;
phi[i] = i - 1;//素数
}
for(int j = 0; j < cnt; j++){
if(i * prime[j] > N)
break;
vis[i * prime[j]] = prime[j];
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];//非素数情况1
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];//非素数情况2
}
}
}
三、同余
定义
对于整数 \(a, b\)，正整数 \(m\)，若 \(m \mid (a - b)\)，则称 \(a\) 和 \(b\) 模 \(m\) 同余，正整数 \(m\) 成为同余的模，记作 \(a \equiv b \pmod m\)
同余的性质
1.自反性： \(a \equiv a \pmod m\)
证：\(\because m \mid (a - a) = 0\)
\(\therefore\) 等式成立
2.对称性：若 \(a \equiv b \pmod m\)，则 \(b \equiv a \pmod m\)
证：\(\because a \equiv b \pmod m\)
\(\therefore m \mid (a - b)\)
设 \(km = a - b\)
\(\therefore (-k)m = b - a\)，即 \(m \mid (b - a)\)
\(\therefore b \equiv a \pmod m\);
\(\therefore\) 等式成立
3.传递性：若 \(a \equiv b \pmod m\)，\(b \equiv c \pmod m\)，则 \(a \equiv c \pmod m\)
证：\(\because a \equiv b \pmod m，b \equiv c \pmod m\)
\(\therefore m \mid (a - b)\) 且 \(m \mid (b - c)\)
设 \(km = a - b，lm = b - c\)
\(\therefore a - c = (a - b) - (b - c) = km - lm = (k - l)m\)，即 \(m \mid (a - c)\)
\(\therefore a \equiv c \pmod m\)
\(\therefore\) 等式成立
4.可加性：若 \(a \equiv b \pmod m，c \equiv d \pmod m\)，则 \(a + c \equiv b + d \pmod m\) (自然两边同时减也是可以的)
证：\(\because a \equiv b \pmod m，c \equiv d \pmod m\)
\(\therefore m \mid (a - b)，m \mid (c - d)\)
设 \(km = a - b，lm = c - d\)
\(\therefore (a + c) - (b + d) = (a - b) + (c - d) = km + lm = (k + l)m\)，即 \(m \mid [(a + c) - (b + d)]\)
\(\therefore a + c \equiv b + d \pmod m\)
\(\therefore\) 等式成立
5.可乘性：若 \(a \equiv b \pmod m，c \equiv d \pmod m\)，则 \(ac \equiv bd \pmod m\)
证：\(\because a \equiv b \pmod m，c \equiv d \pmod m\)
\(\therefore m \mid (a - b)，m \mid (c - d)\)
设 \(km = a - b，lm = c - d\)
\(\therefore ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = ckm + blm = m(ck + bl)\)
\(\therefore m \mid (ac - bd)\)，即 \(ac \equiv bd \pmod m\)
\(\therefore\) 等式成立
6.可除性：若 \(ac \equiv bc \pmod m\)，则 \(a \equiv b \pmod{\displaystyle\frac{m}{\gcd(m, c)}}\)
可除性前置一：若 \(a, b, m, n\) 为整数，且 \(c \mid a，c\mid b\)，则 \(c \mid (ma + nb)\)
证：\(\because c \mid a，c\mid b\)
设 \(a = ce, b = cf(c, e \in Z)\)
\(\therefore ma + nb = mce + ncf = c(me + nf)\)
\(\therefore c \mid (ma + nb)\)
可除性前置二：若 \(a, b, c\) 为正整数，且 \(\gcd(a, b) = 1，a \mid bc\)，则\(a \mid c\)
证：\(\because \gcd(a, b) = 1\)
\(\therefore\) 可以构造出方程组 \(ax + by = 1(x, y \in Z)\) (裴蜀定理)
两边同乘 \(c\) 得：\(acx + bcy = c\)
\(\because a \mid (ac)，a \mid (bc)\)
根据可除性前置一，\(a \mid acx + bcy\)
\(\therefore a \mid c\)
证：\(\because ac \equiv bc \pmod m\)
\(\therefore m \mid (ac - bc) = c(a - b)\)
设 \(km = c(a - b)\)，两边同时除以 \(\gcd(m, c)\)，得：\((c / \gcd(m, c))(a - b) = k(m / \gcd(m, c))\)
\(\because \gcd(m / gcd(m, c)，c / \gcd(m, c)) = 1，(m / \gcd(m, c)) \mid (c / \gcd(m, c))(a - b)\)，根据可除性前置二，得：\((m / \gcd(m, c)) \mid (a - b)\)
\(\therefore a \equiv b \pmod m\)
可除性推论：若 \(a,b,c\) 是整数，\(m\) 是正整数，\(\gcd(c, m) = 1，ac \equiv bc \pmod m\)，则 \(a \equiv b \pmod m\)
费马小定理
内容
对于质数 \(p\)，正整数 \(a\)，若 \(\gcd(a, p) = 1\)，则 \(a^{p - 1} \equiv 1 \pmod p\)
费马小定理也通常被写作 \(a^p \equiv a \pmod p\) (可乘性)
证明
证明：考虑数学归纳法
首先 \(1^{p - 1} \equiv 1 \pmod p\) (显然成立)
假设对于正整数 \(x\) 满足 \(\gcd(x, p) = 1\)，有\(x^{p - 1} \equiv 1 \pmod p\)
\(\because (x + 1)^p \equiv x^p + 1 \pmod p\) (证明Lucas定理时证过，详见组合数学学习笔记（一）（2024.7.3）)
\(\because x^{p - 1} \equiv 1 \pmod p\)
\(\therefore x^p + 1 \equiv x \times x^{p - 1} + 1 \equiv x + 1 \pmod p\)
\(\therefore (x + 1)^p \equiv x + 1 \pmod p\)
\(\therefore (x + 1)^{p - 1} \equiv 1 \pmod p\) (可除性)
符合数学归纳法，等式成立。
逆元
定义
由可除性可知，模意义下的除法受 \(c \mid a, c \mid b\) 限制。
这是我们可以将除 \(c\) 改为乘 \(c\) 的倒数，就可以用乘法完成。
\(c\) 的倒数就成为 \(c\) 在该模数意义下的逆元。
形式化的，若 \(ax \equiv 1 \pmod m\)，则称 \(x\) 为 \(a\) 在模 \(m\) 意义下的逆元。
费马小定理求逆元
\(\because a^{p - 1} \equiv 1 \pmod m\)
\(\therefore a \times a^{p - 2} \equiv 1 \pmod m\)
\(\therefore a^{p - 2}\) 为 \(a\) 在模 \(p\) 意义下的逆元
模板：
#include <bits/stdc++.h>
using namespace std;
int qpow(int x, int p, int m){
int res = 1;
while(p > 0){
if (p % 2 == 1)
res = res * x % m;
p /= 2;
x = x * x % m;
}
return res;
}
int n, p;
int main(){
scanf("%d%d", &n, &p);
printf("%d", qpow(n, p - 2, p));
return 0;
}
扩展欧几里得算法求逆元
\(\because ax \equiv 1 \pmod m\)
\(\therefore p \mid (ax - 1)\)
设 \((-k)p = ax - 1\)
移项得：\(ax + kp = 1\)
\(a\) 和 \(p\) 已知，\(x\) 和 \(k\) 未知，且 \(\gcd(a, p) = 1\)，可以用扩展欧几里得算法求出 \(x\) 和 \(k\)
模板：
#include <bits/stdc++.h>
using namespace std;
int extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
return 0;
}
int d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int mod_inverse(int a, int m){
int x, y;
extend_gcd(a, m, x, y);
return (x % m + m) % m;
}
int n, p;
int main(){
scanf("%d%d", &n, &p);
printf("%d", mod_inverse(n, p));
return 0;
}
递推求逆元
当我们要求 \([1 \dots n]\) 之间所有数在模 \(p\) 意义下的逆元，此时可以用递推求出。
首先，\(1\) 在模 \(p\) 意义下的逆元还是 \(1\)
对于 \(a \neq 1\) 的情况，设 \(k = \lfloor\displaystyle\frac pi \rfloor，j = p \bmod i (i, j, k \in N^+)\)
\(\therefore p = ki + j\)
\(\therefore ki + j \equiv 0 \pmod p\)
两边同乘 \(i^{-1} \times j^{-1}\) (\(x^{-1}\) 表式 \(x\) 在模意义下的逆元)，得：
\(ki \times i^{-1} \times j^{-1} + j * i^{-1} \times j^{-1} \equiv 0 \pmod p\) (可乘性)
\(kj^{-1} + i^{-1} \equiv 0 \pmod p\) (逆元的定义)
\(i^{-1} = -kj^{-1} \pmod p\) (可减性)
带入 \(k, j\) 的定义得：
\(i^{-1} = -\lfloor\displaystyle\frac pi \rfloor(p \bmod i)^{-1} \pmod p\)
\(\because p \bmod i ＜ i\)，且求到 \(i\) 在模 \(p\) 意义下的逆元时已经求出了 \([1 \dots i- 1]\) 之间所有数在模 \(p\) 意义下的逆元，可以线性递推。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 9;
int inv[N], n, p;
int main(){
scanf("%d%d", &n, &p);
inv[1] = 1;
printf("1\n");
for(int i = 2; i <= n; i++){
inv[i] = (p - p / i) * inv[p % i] % p;
printf("%d\n", inv[i]);
}
return 0;
}
欧拉定理（扩展费马小定理）
内容
对于正整数 \(a, p\)，若 \(\gcd(a, p) = 1\)，则 \(a^{\varphi(p)} \equiv 1 \pmod p\) (注意条件与费马小定理的区别)
证明
证：我们知道，\(\varphi(p)\) 表示小于 \(p\) 且与 \(p\) 互质的数的个数，设这 \(\varphi(p)\) 个数分别是 \(x_1, x_2, \dots x_{\varphi(p)}\)
把每个数乘 \(a\) 再对 \(p\) 取模，得 \(ax_1 \bmod p, ax_2 \bmod p, \dots , ax_{\varphi(p)} \bmod p\)
假设 \(ax_1 \bmod p = ax_2 \bmod p\)，即 \(ax_1 = ax_2 \pmod p\)
\(\because gcd(a, p) = 1\)，根据可除性推论，得：\(x_1 = x_2\)，而因为这 \(\varphi(p)\) 个数构成了模 \(p\) 得即约剩余系
\(\therefore x_1 \neq x_2\)，矛盾
\(\therefore ax_1 \bmod p, ax_2 \bmod p, \dots , ax_{\varphi(p)} \bmod p\) 这 \(\varphi(p)\) 个数互不相同
假设 \(\gcd(ax_1 \bmod p, p) = g(g \neq 1)\)
\(\therefore\) 要么 \(g \mid a\)，要么 \(g \mid x_1\)，且 \(g \mid n\)
\(\because \gcd(x_1, n) = 1\)
\(\therefore g \mid x_1\) 与 \(g \mid n\) 不能同时成立
\(\because \gcd(a, n) = 1\)
\(\therefore g \mid a\) 与 \(g \mid n\) 不能同时成立
假设不成立
\(\therefore \gcd(ax_1 \bmod p, p) = 1\)
\(\therefore \{ax_1 \bmod p, ax_2 \bmod p, \dots , ax_{\varphi(p)} \bmod p\} = \{x_1, x_2, \dots x_{\varphi(p)}\}\)，都是 \(p\) 的既约剩余系
\(\therefore ax_1 \times ax_2 \times \dots \times ax_{\varphi(p)} \equiv x_1 \times x_2 \times \dots \times x_{\varphi(p)} \pmod p\)
\(\therefore a^{\varphi(p)} \equiv 1 \pmod p\) (两边同除 \(x_1 \times x_2 \times \dots \times x_{\varphi(p)}\))
威尔逊定理
内容
若 \(p\) 是素数，则 \((p - 1)! \equiv -1 \pmod p\)
定理3.5.1
对于整数 \(a, b\)，正整数 \(m\)，设 \(\gcd(a, m) = d\)，若 \(d \nmid b\)，则 \(ax \equiv b \pmod m\) 无解，若 \(d \mid b\)，则 \(ax \equiv b \pmod m\) 恰好有 \(d\) 个模 \(m\) 不同余的解。
证：\(\because ax \equiv b \pmod m\)
\(\therefore m \mid (ax - b)\)
设 \(my = ax - b\)
移项得：\(ax - my = b\)
整数 \(x\) 是 \(ax \equiv b \pmod m\) 的解当且仅当存在 \(y\) 使得 \(ax - my = b\)，由裴蜀定理可得，若 \(d \nmid b\)，则无解，而 \(d \mid b\) 时，\(ax - my = b\) 有无穷多解:\(x = x_0 + (m / d)t，y = y_0 + (a / d) t\)
其中 \(x = x_0\) 和 \(y = y_0\) 是方程的特解，上述 \(x\) 的值是 \(ax \equiv b \pmod m\) 的解，有无穷多这样的解。
设两个解 \(x_1 = x0 + (m / d)t_1，x_2 = x_0 + (m / d)t_2\)，假设这两个解在模 \(m\) 意义下同余，则：\(x_0 + (m / d)t_1 \equiv x_0 + (m / d)t_2 \pmod m\)
\(\therefore (m / d)t_1 \equiv (m / d)t_2 \pmod m\)
\(\because \gcd(m / d, d) = m / d\)
\(\therefore t_1 \equiv t_2 \pmod m\)(可除性)
这表明 \(ax \equiv b \pmod m\) 在模 \(p\) 意义下不同余的解的完全集合可以通过 \(x = x_0 + (m / d)t(t \in [0, d)\) 且 \(t \in Z\)) 给出。
\(\therefore ax \equiv b \pmod m\) 恰好有 \(d\) 个模 \(m\) 不同余的解。
推论：对于整数 \(a, b\)，正整数 \(m\)，若 \(\gcd(a, m) = 1\)，则 \(ax \equiv b \pmod m\) 有模 \(m\) 的唯一解。
定理3.5.2
对于素数 \(p\)，正整数 \(a\) 是其自身模 \(p\) 意义下的逆元当且仅当 \(a \equiv 1 \pmod p\) 或 \(a \equiv 1 \pmod p\)
证：若 \(a \equiv 1 \pmod p\) 或 \(a \equiv 1 \pmod p\)，则 \(a^2 \equiv 1 \pmod p\)，所以 \(a\) 是其自身在模 \(p\) 意义下的逆元。
反过来，若 \(a\) 是其自身在模 \(p\) 意义下的逆元，则 \(a ^ 2 \equiv 1 \pmod p\)
\(\therefore p \mid (a^2 - 1)\)
\(\because a^2 = (a + 1)(a - 1)\)
\(\therefore p \mid (a + 1)\) 或 \(p \mid (a - 1)\)
\(\therefore a \equiv 1 \pmod p\) 或 \(a \equiv -1 \pmod p\)(\(a \equiv -1 \pmod p\) 也可以写作 \(a \equiv p-1 \pmod p\))
证明
证：当 \(p = 2\) 时，\((p - 1)! \equiv 1 \equiv -1 \pmod 2\)
当 \(p \geq 3\) 时，根据定理3.5.1推论可得，对于 \(a(a \in [1,p)\) 且 \(a \in Z\))，存在 \(a^{-1}(a^{-1} \in [1,p)\) 且 \(a^{-1} \in Z\))，使得 \(a^{-1}a \equiv 1 \pmod p\)
根据定理3.5.2可得，在小于 \(p\) 的正整数中，在模 \(p\) 意义下的逆元是其本身的数只有 \(1\) 和 \(p - 1\)
\(\therefore\) 可以将 \(2\) 到 \(p - 2\) 分成 \((p - 3) / 2\) 组整数对且每组整数对都是一对模 \(p\) 意义下的逆元
\(\therefore 2 \times 3 \times \dots \times (p - 3) \times (p - 2) \equiv 1 \pmod p\)
将同余式两边同乘 \(1\) 和 \(p - 1\)，得：\((p - 1)! = 1 \times 2 \times 3 \times \dots \times (p - 3) \times (p - 2) \times (p - 1) \equiv -1 \pmod p\)
威尔逊定理逆定理
内容
对于正整数 \(n\)，\(n \geq 2\)，若 \((n - 1)! \equiv -1 \pmod n\)，则 \(n\) 是素数。
定理3.5.3
对于整数 \(a, b, c\)，若 \(a \mid b，b \mid c\)，则 \(a \mid c\)
证：\(\because a \mid b，b \mid c\)
设 \(b = ae，c = bf\)
\(\therefore c = bf = (ae)f = a(ef)\)
\(\therefore a \mid c\)
证明
假设 \(n\) 是一个合数，且 \((n - 1)! \equiv -1 \pmod n\)
假设 \(n = ab(a, b \in Z\) 且 \(a, b \in (1, n)\))
\(\therefore a\) 是组成 \((n - 1)!\) 的 \(n - 1\) 个数中的一个
\(\therefore a \mid (n - 1)!\)
\(\because (n - 1)! \equiv -1 \pmod n\)
\(\therefore n \mid ((n - 1)! + 1)\)
\(\because a \mid n\)
\(\therefore\) 根据定理3.5.3可得：\(a \mid (n - 1)! + 1\)
\(\because a \mid (n - 1)!\) 且 \(a \mid (n - 1)! + 1\)
\(\therefore\) 根据定理1.2.1可得：\(a \mid ((n - 1)! + 1) - (n - 1)! = 1\)，与 \(a \in (1, n)\)矛盾，假设不成立。
\(\therefore n\) 是素数。
中国剩余定理
内容
中国剩余定理是用来求解以下方程：(\(m_1, m_2, \dots, m_n\)是两两互质数)
\[\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \,\,\,\,\,\,\vdots\\ x \equiv a_n \pmod{m_n} \end{cases} \]定理3.6.1
对于整数 \(a, b, c\)，若 \(\gcd(a, b) = 1\) 且 \(c \mid (a + b)\)，则 \(\gcd(a, c) = \gcd(b, c) = 1\)
证：
解法
解：令 \(M = p_1 \times p_2 \times \dots \times p_n\)，\(M_i = \displaystyle\frac{M}{m_i}\)
\(\therefore\) 根据定理3.6.1可得：\(\gcd(M_i, m_i) = 1\)
\(\therefore\) 根据定理3.5.1推论，\(M_i\) 存在唯一一个在模 \(m_i\) 意义下的逆元 \(M_i^{-1}\)，令 \(x = a_iM_iM_i^{-1}\)，带回原方程，可得
\[\begin{cases} x \equiv 0 \pmod{m_1}\\ x \equiv 0 \pmod{m_2}\\ \,\,\,\,\,\,\vdots\\ x \equiv a_i \pmod{m_i}\\ \,\,\,\,\,\,\vdots\\ x \equiv 0 \pmod{m_n} \end{cases} \]可以发现此时 \(x_i\) 的取值只影响第 \(i\) 个同余方程，于是我们可以求出原方程得一组特解 \(x = a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + \dots + a_nM_nM_n^{-1} = \displaystyle\sum_{i=1}^na_iM_iM_i^{-1}\)
通解 \(x = \displaystyle\sum_{i=1}^na_iM_iM_i^{-1} + kM(k \in Z)\)
四、原根
前置知识：阶
定义
对于整数 \(a(a \neq 0)\)，正整数 \(n\)，\(\gcd(a, n) = 1\)，使得 \(a^x \equiv 1 \pmod n\) 成立的最小正整数 \(x\) 称为 \(a\) 模 \(n\) 的阶，记为 \(\operatorname{ind}_na\)
阶的性质
1.对于整数 \(a(a \neq 0)\)，正整数 \(n\)，\(\gcd(a, n) = 1\)，那么正整数 \(x\) 是同余方程 \(a^x \equiv 1 \pmod n\) 的一个解当且仅当 \(\operatorname{ind}_na \mid x\)
证：若 \(\operatorname{ind}_na \mid x\)，则 \(x = k\operatorname{ind}_na \mid x(k \in N^+)\)
\(\therefore a^x = a^{k\operatorname{ind}_na} = (a^{\operatorname{ind}_na})^k \equiv 1 \pmod n\)
反过来，若 \(a^x \equiv 1 \pmod n\)，设 \(x = q\operatorname{ind}_na + r(0 \leq r < \operatorname{ind}_na)\)
\(\therefore a^x = a^{q\operatorname{ind}_na + r} = (a^{\operatorname{ind}_na})^qa^r \equiv a^r \pmod n\)
\(\therefore a^r \equiv 1 \pmod n\)
\(\therefore\) 根据阶的定义以及 \(0 \leq r < \operatorname{ind}_na\)，\(r = 0\)
\(\therefore x = q\operatorname{ind}_na\)
\(\therefore \operatorname{ind}_na \mid x\)
2.对于整数 \(a(a \neq 0)\)，正整数 \(n\)，\(\gcd(a, n) = 1\)，那么 \(a^i \equiv a^j \pmod n(i, j \in N)\) 当且仅当 \(i \equiv j \pmod{\operatorname{ind}_na}\)
证：若 \(i \equiv j \pmod{\operatorname{ind}_na}\) 且 \(0 \leq j \leq i\)，设 \(i = j + k\operatorname{ind}_na(k \in N^+)\)
\(\therefore a^i = a^{j + k\operatorname{ind}_na} = a^j (a^{\operatorname{ind}_na})^k \equiv a^j \pmod n\)
反过来，若 \(a^i \equiv a^j \pmod n\) 且 \(i \geq j\)
\(\because \gcd(a, n) = 1\)
\(\therefore \gcd(a^j, n) = 1\)
\(\because a^j \equiv a^i \equiv a^ja^{i - j} \pmod n\)
\(\therefore\) 根据可除性推论，\(a^{i - j} \equiv 1 \pmod n\)
\(\therefore\) 根据阶的性质1，\(\operatorname{ind}_na \mid (i - j)\)
\(\therefore i \equiv j \pmod{\operatorname{ind}_na}\)
原根
定义
对于整数 \(a(a \neq 0)\)，正整数 \(n\)，\(\gcd(a, n) = 1\)，当 \(\operatorname{ind}_na = \phi(n)\) 时，称 \(a\) 是模 \(n\) 的原根或者 \(n\) 的原根，并且我们称 \(n\) 有一原根。
定理4.2.1
对于整数 \(a, b\)，正整数 \(k, m\)，若 \(a \equiv b \pmod m\)，则 \(a^k \equiv b^k \pmod m\)
证：\(\because a \equiv b \pmod m\)
\(\therefore m \mid (a - b)\)
\(\therefore a^k - b^k = (a - b)(a^{k - 1} + a^{k - 2}b + \dots + ab^{k - 2} + b^{k - 1})\)
\(\therefore (a - b) \mid (a^k - b^k)\)
\(\therefore\) 根据定理3.5.3，\(m \mid (a^k - b^k)\)
\(\therefore a^k \equiv b^k \pmod m\)
原根的存在性
1.设 \(p\) 是一个素数且 \(d\) 是 \(p - 1\) 的一个正因子，那么模 \(p\) 的阶为 \(d\) 且不同余的整数的个数为 \(\varphi(d)\)
证：设 \(F(d)\) 表示小于 \(p\) 且模 \(p\) 的阶为 \(d\) 的正整数的个数。
\(\because\) 一个不能被 \(p\) 整除的整数模 \(p\) 的阶整除 \(p - 1\)
\(\therefore p - 1 = \displaystyle\sum_{d \mid (p - 1)} F(d)\)
\(\because\) 根据欧拉函数性质5，有 \(p - 1 = \displaystyle\sum_{d \mid (p - 1)} \varphi(d)\)
\(\therefore\) 根据阶的性质1，当 \(d \mid (p - 1)\) 时有 \(F(d) \leq \varphi(d)\)
\(\therefore F(d) = \varphi(d)\)，即对于 \(p - 1\) 的每一个正因子 \(d\)，有 \(F(d) = \varphi(d)\)
\(\therefore\) 模 \(p\) 的阶为 \(d\) 且不同余的整数的个数为 \(\varphi(d)\)
原根的存在性1推论：每个素数都有原根
2(扩展).如果正整数 \(n\) 不是一个素数的幂或者不是一个素数的幂的两倍(幂可以为 \(0\))，那么 \(n\) 不存在原根。
证：设 \(n\) 的唯一分解是 \(\displaystyle\prod_{i=1}^m p_i^{c_i}\)，假设 \(n\) 有一个原根 \(r\)，即存在一个正整数 \(r\) 使得 \(\gcd(r, n) = 1\) 且 \(\operatorname{ind}_nr = \varphi(n)\)
\(\therefore \gcd(r, p_i^{c_i}) = 1\)
\(\therefore\) 根据欧拉定理，\(r^{\varphi(p_i^{c_i})} \equiv 1 \pmod{p_i^{c_i}}\)
设 \(U = \operatorname{lcm}(\varphi(p_1^{c_1}), \varphi(p_2^{c_2}), \dots, \varphi(p_m^{c_m}))\)
\(\because \varphi(p_i^{c_i}) \mid U\)
\(\therefore r^U \equiv 1 \pmod{p_i^{c_i}}\)
\(\therefore\) 根据定理4.2.1，有 \(r^U \equiv 1 \pmod n\)
\(\therefore \operatorname{ind}_nr = \varphi(n) \leq U\)
\(\therefore\) 根据欧拉函数性质3，有 \(\varphi(n) = \varphi(p_1^{c_1}, p_2^{c_2}, \dots, p_m^{c_m}) = \varphi(p_1^{c_1})\varphi(p_2^{c2})\dots\varphi(p_m^{c_m})\)
\(\therefore \varphi(p_1^{c_1})\varphi(p_2^{c2})\dots\varphi(p_m^{c_m}) \leq \operatorname{lcm}(\varphi(p_1^{c_1}), \varphi(p_2^{c_2}), \dots, \varphi(p_m^{c_m}))\)
\(\because\) 一组数的乘积等于它的最大公倍数当且仅当这一组数两两互质。
\(\therefore \varphi(p_1^{c_1}), \varphi(p_2^{c_2}), \dots, \varphi(p_m^{c_m})\) 两两互质。
\(\because\) 根据欧拉函数性质2，有 \(\varphi(p_i^{c_i}) = p_i^{c_i - 1}(p_i - 1)\)
\(\therefore \varphi(p_i^{t_i})\) 是偶数只有在 \(p\) 是奇数或 \(p = 2\) 且 \(t \geq 2\) 时成立除去 \(m = n\) 或 \(1\) 这两种素数的幂情况，以及 \(m = 2\) 或 \(n = 2p_i^{c_i}\) 这两种情况，\(\varphi(p_1^{c_1}), \varphi(p_2^{c_2}), \dots, \varphi(p_m^{c_m})\) 两两不互质.
\(\therefore\) 如果正整数 \(n\) 不是一个素数的幂或者不是一个素数的幂的两倍(幂可以为 \(0\))，那么 \(n\) 不存在原根。
定理4.2.2
对于正整数 \(u\)，若 \(\operatorname{ind}_na = t\)，则 \(\operatorname{ind}_n(a^u) = t / \gcd(t, u)\)
证：设 \(s = \operatorname{ind}_n(a^u), v = \gcd(t, u), t = t_1v, u = u_1v\)
\(\because \gcd(t, u) = v\)
\(\therefore \gcd(t_1, u_1) = v\)
\(\because (a^u)^{t_1} = (a^{u_1v})^{(t / v)} = (a^t)^{u_1} \equiv 1 \pmod n\)
\(\therefore\) 根据阶的性质1，\(s \mid t_1\)
\(\because (a^u)^s = a^{us} \equiv 1 \pmod n\)
\(\therefore\) 根据阶的性质1，\(t \mid us\)
\(\therefore t_1u \mid u_1vs\)
\(\therefore t_1 \mid u_1s\)
\(\because \gcd(t_1, u_1) = 1\)
\(\therefore\) 根据可除性前置二，\(t_1 \mid s\)
\(\because s \mid t_1\) 且 \(t_1 \mid s\)
\(\therefore s = t_1 = t / u = t / \gcd(t, u)\)
定理4.2.2推论：若 \(r\) 是 \(n(n > 1)\) 的原根，则 \(r^u\) 是 \(n\) 的原根当且仅当 \(\gcd(u, \varphi(n)) = 1\)
定理4.2.3
对于正整数 \(r, n\)，\(\gcd(n, r) = 1\)，若 \(r\) 是 \(n\) 的一个原根，则 \(r, r^2, \dots, r^{\varphi(n)}\) 构成了模 \(n\) 的既约剩余系。
证：\(\because \gcd(r, n) = 1\)
\(\therefore \gcd(r^k, n) = 1(k \in N^+)\)
\(\therefore\) 这些幂都与 \(n\) 互质。
假设有 \(r^i \equiv r^j \pmod n\)
\(\therefore\) 根据阶的性质2，\(i \equiv j \pmod{\operatorname{ind}_nr}\)
\(\because r\) 是 \(n\) 的原根。
\(\therefore \operatorname{ind}_nr = \varphi(n)\)
\(\because 1 \leq i, j \leq \varphi(n)\)
\(\therefore i = j\)
\(\because\) 没有两个数的指数是相同的。
\(\therefore\) 每个数都不模 \(n\) 同余。
\(\therefore\) 这些数构成了模 \(n\) 的既约剩余系。
原根的个数
对于正整数 \(n\)，若它有一个原根，那它一共有 \(\varphi(\varphi(n))\) 个不同余的原根。
证：\(\because r\) 是 \(n\) 的原根。
\(\therefore\) 根据定理4.2.4，\(r, r^2, \dots, r^{\varphi(n)}\) 构成了模 \(n\) 的既约剩余系。
\(\because\) 根据定理4.2.2推论，\(r^u\) 是 \(n\) 的原根当且仅当 \(\gcd(u, \varphi(n)) = 1\)
\(\therefore\) 满足条件的 \(u\) 有 \(\varphi(\varphi(n))\) 个。
\(\therefore n\) 一共有 \(\varphi(\varphi(n))\) 个不同余的原根。
定理4.2.4(拉格朗日定理)
假设 \(f(x) = \displaystyle\sum_{i=0}^na_ix^i\) 是一个次数为 \(n\) 且首项系数 \(a_n \nmid p\) 的整系数多项式，\(n \geq 1\)，那么 \(f(x)\) 至多有 \(n\) 个模 \(p(p \in \mathbb{P})\) 不同余的根。
证：考虑数学归纳法。
当 \(n = 1\) 时，\(f(x) = a_1x + a_0\) 且 \(p \nmid a_1\)
\(\therefore f(x)\) 模 \(p\) 的一个根就是同余方程 \(a_1x \equiv -a_0 \pmod p\) 的解。
\(\because \gcd(a_1, p) = 1\)
\(\therefore\) 根据定理3.5.1，同余方程 \(a_1x \equiv -a_0 \pmod p\) 恰有一个解。
\(\therefore f(x)\) 模 \(p\) 也恰有一根，定理成立。
当 \(n > 1\) 时，假设定理对 \(n - 1\) 次多项式成立，设 \(f(x)\) 是一个次数为 \(n\) 且首项系数不被 \(p\) 整除的多项式，\(g(x)\) ，假设这个多项式 \(f(x)\) 有 \(n + 1\) 个模 \(p\) 不同余的根，记为 \(c_0, c_1, c_2, \dots, c_n\)
\(\therefore f(x) - f(c_0) = \displaystyle\sum_{i=1}^na_i(x^i - c_0^i) = \\a_n(x - c_0)(x^{n - 1} + x^{n - 2}c_0 + \dots + xc_0^{n - 2} + c_0^{n - 1})\\ + a_{n - 1}(x - c_0)(x^{n - 2} + x^{n - 3}c_0 + \dots + xc_0^{n - 3} + c_0^{n - 2})\\ + \dots + a_1(x - c_0) = (x - c_0)g(x)\)
设 \(k\) 是一个整数且 \(1 \leq k \leq n\)
\(\because f(c_k) \equiv f(c_0) \equiv 0 \pmod p\)
\(\therefore f(c_k) - f(c_0) = (c_k - c_0)g(c_k) \equiv 0 \pmod p\)
\(\because c_0\) 和 \(c_k\) 是不同的根。
\(\therefore c_k - c_0 \neq 0\)
\(\therefore g(c_k) \equiv 0 \pmod p\)
\(\therefore c_k\) 是 \(g(x)\) 模 \(p\) 的一个根。
\(\therefore\) 一个次数为 \(n - 1\) 且首项系数不能被 \(p\) 的多项式 \(g(x)\) 有 \(n\) 个模 \(p\) 不同余的根，与数学归纳法的假设相矛盾，不成立。
\(\therefore f(x)\) 至多有 \(n\) 个模 \(p(p \in \mathbb{P})\) 不同余的根。
定理4.2.5
对于素数 \(p\)，\(d\) 是 \(p - 1\) 的因子，那么多项式 \(f(x) = x^d - 1\) 恰有 \(d\) 个模 \(p\) 不同余的根。
证：设 \(p - 1 = de\)
\(\therefore x^{p - 1} - 1 = (x^d - 1)(x^{d(e - 1)} + x^{d(e - 2)} + \dots + x^d + 1) = (x^d - 1)g(x)\)
\(\because\) 根据费马小定理，\(x^{p - 1}\) 有 \(p - 1\) 个模 \(p\) 不同余的根，这些根就是 \(x^d - 1\) 模 \(p\) 不同余的根与 \(g(x)\) 模 \(p\) 不同余的根的并集
\(\therefore\) 根据拉格朗日定理，\(g(x)\) 模 \(p\) 不同余的根至多有 \(d(e - 1) = p - 1 - d\) 个
\(\therefore\) 多项式 \(f(x) = x^d - 1\) 的根至少有 \((p - 1) - (p - 1 - d)\) 个模 \(p\) 不同余的根。
\(\therefore\) 根据拉格朗日定理，\(f(x) = x^d - 1\) 至多有 \(d\) 个模 \(p\) 不同余的根。
\(\therefore x^d - 1\) 恰好有 \(d\) 个模 \(p\) 不同余的根。
原根的应用
观察定理4.2.5的式子，它的形式和单位根完全一样。
由于形如 \(p^t\) 的数都是原根，所以原根可以通过乘法递推，将原根带入 \(x\) 后，可以发现原根的所有幂都满足该方程，且模 \(p\) 不同余的数恰好有 \(p\) 个，因此，解决模意义下的多项式乘法可以用原根替代单位根
参考资料
-
A Friendly Introduction to Number Theory(Fourth edition) Joseph H. Silverman
-
Elementary Number Theory and Its Application(Sixth Edition) Kenneth H. Rosen
-
初等数论学习笔记 I：同余相关 Alex_wei
-
初等数论学习笔记 III：数论函数与筛法 Alex_wei
-
琴生不等式 百度百科
-
筛法 OI Wiki