基础数论学习笔记 - 洛谷保存站

[cnblogs](https://www.cnblogs.com/StarsIntoSea/p/18946566)。

# 前言

大部分定理的证明是参考的相关资料，因为我是菜狗 qwq，但都是在学习后自己独立写出来的。

因为写的时候是在不同时间写的，所以通读的时候会有一点割裂感。

我一开始写只是方便自己快速复习的，但是写着写着就感觉是在给别人看一样，也不重要了。

带 * 的是不知道放哪里，又感觉另开一个大章太费事，放在需要以这个大章为核心知识的地方。

有错会及时修正，后面的 BSGS 等更高级的如果考完 NOIP 后没退役就会更新。

# 1 数论中的基础知识

## 1.1 整除

### 1.1.1 定义

设 $a,b$ 是整数，如果存在一个整数 $c$，使得 $b=ac$，则我们称为 $a$ 整除 $b$（或 $b$ 被 $a$ 整除），记作 $a\mid b$。

### 1.1.2 定理

1. （反射性）对于所有整数 $a$，满足 $a \mid a$。
2. （传递性）若 $a \mid b$，$b \mid c$，则 $a \mid c$。
3. 若 $a,b_1,b_2,\cdots,b_n$ 都是整数，并且 $a \mid b_i $（$1 \le i \le n$），则 $a \mid b_1c_1+b_2c_2+\cdots+b_nc_n$ 对于所有整数 $c_1,c_2,\cdots,c_n$ 成立。
4. 若 $a,b_1,b_2,\cdots,b_n$ 都是整数，并且 $a \mid b_i $（$1 \le i \le n$），则 $a \mid b_1c_1\times b_2c_2 \times \cdots \times b_nc_n$ 对于所有整数 $c_1,c_2,\cdots,c_n$ 成立。
5. 若 $a \mid b$，$a \mid b \pm c$，则 $a \mid c$。
6. 若整数 $a,b,c,d,e$ 满足 $a \mid b-c$，$a \mid d-e$，则 $a \mid bd - ce$。
7. 若 $a\mid b$，则对于任意整数 $c$，满足 $ac\mid bc$。若 $ac \mid bc$，且 $c \ne 0$，则 $a\mid b$。

### 1.1.3 证明

定理 1、2、7 可以从定义入手。

**定理 3、4 的证明如下：**

令 $w_1,w_2,\cdots,w_n$ 为满足下列条件的整数：
$$
\begin{aligned}
  \ b_1 &= a w_1 \\
  \ b_2 &= a w_2 \\
  &\cdots \\
  \ b_n &= a w_n
\end{aligned}
$$
则有：
$$
\begin{aligned}
  \ b_1 c_1 &= a w_1 c_1\\
  \ b_2 c_2 &= a w_2 c_2\\
  &\cdots \\
  \ b_n c_n &= a w_n c_n
\end{aligned}
$$
相加/相乘得：
$$
\begin{aligned}
 \sum_{i=1}^{n} b_ic_i &= \sum_{i=1}^{n} aw_ic_i \\
 &=a \times \sum_{i=1}^{n} w_ic_i \\
 \prod_{i=1}^{n} b_ic_i &= \prod_{i=1}^{n} aw_ic_i \\
 &= a^n \times  \prod_{i=1}^{n} w_ic_i \\
 &= a \times a^{n-1} \prod_{i=1}^{n} w_ic_i
\end{aligned}
$$
证毕。

**定理 5 证明如下：**

令 $w_1,w_2$ 为满足 $b=aw_1,b+c=aw_2$ 的整数。

令 $c=qa$，则有$b=aw_1=aw_2-qa=a(w2-q)$。

$\therefore w_1=w_2-q$。

$\because w_1,w_2$ 为整数。

$\therefore q$ 为整数，$w_2-q$ 也是整数。

$-c$ 同理，证毕。

**定理 6 证明如下：**

令 $w_1,w_2$，为满足 $b-c=aw_1,d-e=aw_2$ 的整数。

则有：
$$
\begin{aligned}
 b &= aw_1+c \\ d &= aw_2+e \\ \\
 bd &= (aw_1+c)(aw_2+e) \\
  bd  &= a^2w_1w_2+aw_1e+aw_2c+ce \\
 bd - ce &= a^2w_1w_2+aw_1e+aw_2c\\
 bd-ce &= a(aw_1w_2+w_1e+w_2c)
\end{aligned}
$$
证毕。

## 1.2 同余

### 1.2.1 定义

设 $a,b,n$ 是整数，若 $n \mid a-b$，则称 $a$ 和 $b$ 模 $n$ 同余，记作：
$$
a \equiv b \pmod {n} 
$$
### 1.2.2 定理

1. （反射性）$a \equiv a \pmod n$。
2. （对称性）若 $a \equiv b \pmod n$，则 $b \equiv a \pmod n$。
3. （传递性）若 $a \equiv b \pmod n$，且 $b \equiv c \pmod n$，则 $a \equiv c  \pmod n$。
4. 若 $a \equiv c \pmod n$，且 $b \equiv d \pmod n$，则 $a+b \equiv c+d \pmod n$，$ab \equiv cd \pmod n$。
5. 若 $a \equiv b \pmod n$，则 $ ac \equiv bc \pmod {nc}$。若 $ac \equiv bc \pmod {nc}$，且 $c \ne 0$，则 $a \equiv b \pmod n$。

### 1.2.3 证明

定理 1、2 可以从定义入手。

**定理 3 证明如下：**

根据定义 $n \mid a-b$，$n \mid b-c$。

由整除的定理 3 可以得到：
$$
n \mid (a-b)+(b-c) \\ 
n \mid a-c
$$
证毕。

**定理 4 的证明如下：**

根据定义 $n \mid a-c$，$n \mid b-d$。

由整除的定理 3 可以得到：
$$
n \mid a-c+b-d \\
n \mid (a+b)-(c+d)
$$
由整除的定理 6 可以得到：
$$
n \mid ab - cd
$$
证毕。

定理 5 的证明可以由整除的定理 7 得到。

## 1.3 数论函数

定义域为正整数，值域为复数集的子集的函数称为数论函数。

### 1.3.1 积性函数

对于一个数论函数 $f$，若 $\forall x,y \in \mathbb{N}_+$ 且 $x$ 与 $y$ 互质，都有 $f(xy)=f(x)f(y)$，则称 $f$ 为**积性函数**。

对于一个数论函数 $f$，若 $\forall x,y \in \mathbb{N}_+$，都有 $f(xy)=f(x)f(y)$，则称 $f$ 为**完全积性函数**。

可以看出完全积性函数一定是积性函数。

积性函数一定满足 $f(1)=1$。

一些常见的积性函数：

1. 1 函数（完全积性）：$\mathbb{1}(n)=1$。
2. 幂函数（完全积性）：$id_k(n)=n^k$。
3. 狄利克雷卷积单位元（完全积性）：$\varepsilon(n)= \begin{cases} 1 \;, n=1 \\ 0 \;, n \not = 1\end{cases}$。
4. 欧拉函数：$\varphi(n)=$ $1 \sim n$ 中与 $n$ 互质的数的个数。
5. 最大公因数：$\gcd_k(n) =\gcd(n,k)$。
6. 除数函数：$d(n)=$ 正整数 $n$ 的正因子个数。

### 1.3.2 加性函数

对于一个数论函数 $f$，若 $\forall x,y \in \mathbb{N}_+$ 且 $x$ 与 $y$ 互质，都有 $f(xy)=f(x)+f(y)$，则称 $f$ 为**加性函数**。

对于一个数论函数 $f$，若 $\forall x,y \in \mathbb{N}_+$，都有 $f(xy)=f(x)+f(y)$，则称 $f$ 为**完全加性函数**。

可以看出完全加性函数一定是加性函数。

加性函数一定满足 $f(1)=0$。

两个常见加性函数：

1. $\Omega(n) =$ 所有素因子（含重复）的总个数。（完全加性）
2. $\omega(n) =$ 不同素因子的个数。

例如 $12=2^2 \times 3,\Omega(12)=3,\omega(12)=2$、$30=2 \times 3 \times 5, \Omega(30)=3,\omega(30)=3$。

## 1.4 模运算

带余除法：对于整数 $a$ 和 $b>0$，则存在唯一的整数 $q,r$，满足 $a=bq+r$，其中 $0 \le r <b$，其中 $q$ 为商，$r$ 为余数。

余数 $r$ 用 $a \bmod b$ 来表示。

带余除法非常重要，在很多题目中都能用带余乘法拆分得到关键步骤。

一些运算法则：

1. $(a+b) \bmod M = (a \bmod M + b \bmod M ) \bmod M$。
2. $(a-b) \bmod M = (a \bmod M - b \bmod M ) \bmod M$。
3. $(a \times b) \bmod M = (a \bmod M \times b \bmod M ) \bmod M$。

**千万千万要注意除法没有类似的运算法则！！！！**

关于除法的模运算详见“模意义下的乘法逆元”。

# 2 素数

对于正整数 $p>1$，若 $p$ 的因数只有 $1$ 和它本身，则 $p$ 是素数。

## 2.1 唯一分解定理

> 每个大于 $1$ 的整数都能唯一的表示成其质因数之积。

即 $n=\prod p_i^{a_i}$ ( $p_i$ 为素数且$p_1<p_2<\cdots,a_i \ge 1$ )。

结论比较显然，故不给出该定理的证明。

求解代码：
```cpp
void decompose(int x){
	for(int i=2;i*i<=x;++i)
		while(x%i==0) ++a[i],x/=i;
	if(x) ++a[x];
}
int main(){
	int n;scanf("%d",&n);
	decompose(n);
	for(int i=1;i<=n;++i) 
		if(a[i]) printf("%d %d\n",a[i],i);
}
```

- 一个真命题： $n$ 中最多含有一个大于 $\sqrt n$ 的因子。

证明：如果存在两个大于 $\sqrt n$ 的因子，则二者相乘大于 $n$，矛盾。

## 2.2 费马小定理

> 若一个素数 $p$，$a$ 是与 $p$ 互质的任意整数，有 $a^{p-1} \equiv 1 \pmod p$。等价地，$a^p \equiv a \pmod p$。

- 对于每一个整数 $i \in [1,p)$，满足 $i \times a \bmod p$ 互不相同。

证明：如果存在整数 $i \ne j $ 且 $i,j \in [1,p)$，满足 $i \times a \equiv j \times a \pmod p$，则 $i \equiv j \pmod p$，不符合定义。

显然有：
$$
\prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1} (i\times a) \equiv a^{p-1} \prod_{i=1}^{p-1}i \pmod p
$$
根据同余的定理 5 可以得到：
$$
\begin{aligned}
a^{p-1} &\equiv 1 \pmod p \\
a^p &\equiv a \pmod p
\end{aligned}
$$
得证费马小定理。

实际上，费马小定理是欧拉定理的一种特殊情况，后文的欧拉定理会提及。

## 2.3 素数筛

### 2.3.1 普通筛

既然是筛法，就不能一个数一个数暴力求是不是素数，这个复杂度 $O(n \sqrt n)$ ~~妥妥 T 飞~~。

一个大于 $1$ 的整数显然要么素数，要么是合数。

根据素数定义，一个数是素数当且仅当其因数只有 $1$ 和它本身。

那么对于任意大于 $1$ 的整数 $i,j$，$i \times j$ 必定不是素数，那么它就是合数，这样就得到了时间复杂度为 $O(n \log n)$ 普通筛：

```cpp
for(int i=2;i<=n;++i){
  if(!vis[i]) prime[++tot]=i; //没有被标记合数就是素数
  for(int j=2;j*i<=n;++j)   //枚举 i 的所有倍数 i*j  
    vis[j*i]=1;         //i 的倍数必定是合数
}
```

### 2.3.2 埃氏筛

上面的筛法也太慢了，比如 $12=3\times 4$，$i=3$ 或 $i=4$ 时都会把 $12$ 筛去，我们需要更快的筛法。

不难发现，根据唯一分解定理，一个合数一定会被拆成若干质因子之积。

这样就可以把质数的倍数筛出来，就可以避免前文的例子中 $i=4$ 这样枚举合数的倍数这种纯浪费时间的情况。

时间复杂度 $O(n \log \log n)$，作者不会证复杂度 qwq。

```cpp
for(int i=2;i<=n;++i){
	if(!vis[i]){
		prime[++tot]=i;
		for(int j=2;j*i<=n;++j) //枚举素数的整数倍
			vis[i*j]=1;
	}
}
```
既然素数的（大于 $1$ 的）整数倍是合数，那么（大于 $1$ 的）整数的素数倍也是合数，那么就可以得到埃氏筛的另外一种形式：

```cpp
for(int i=2;i<=n;++i){
	if(!vis[i]) prime[++tot]=i;
	for(int j=1;j<=tot && i*prime[j]<=n;++j)
		vis[i*prime[j]]=1;
}
```

### 2.3.3 线性筛

埃氏筛已经够优秀了，但是带个常数还是太慢了，有没有什么更加快速的筛法吗。

有的兄弟有的，线性筛的复杂度只有 $O(n)$。

线性筛的代码与埃氏筛形式 2 相比只多了一行：

```cpp
for(int i=2;i<=n;++i){
		if(!vis[i]) prime[++tot]=i;
		for(int j=1;j<=tot && i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;   //神奇的一行！
		}
	}
```

线性筛的思想是，对于一个合数 $n$，设 $n$ 的最小质因子为 $p_n$，则 $n$ 会且仅会在 $i=\frac{n}{p_n}$ 被筛去。

正确性是显然的，接下来证明充要性。

充分性证明（合数 $n$ 会在 $i=\frac{n}{p_n}$ 时被筛去）：因为 $p_n$ 是 $n$ 的最小质因子，所以 $\frac{n}{p_n}\ge p_n$，那么在 $i=\frac{n}{p_n}$ 时，$p_n$ 就已经被记录为素数了。且根据唯一分解定理，$\frac{n}{p_n}$ 的质因子一定大于等于 $p_n$。

当 $i=\frac{n}{p_n}$ 时，如果出现 $prime[j]$ 还没有枚举到 $p_n$ 就终止，那么此时 $prime[j] < p_n$ 且 $prime[j]$ 一定是 $i=\frac{n}{p_n}$ 的一个质因子，这与 $p_n$ 是 $n$ 的最小质因子矛盾。得证。

必要性证明（合数 $n$ 仅会在 $i=\frac{n}{p_n}$ 时被筛去）：假设 $p'$ 是 $n$ 的一个质因子且 $p'>p_n$，那么根据唯一分解定理，$p_n$ 也一定是 $\frac{n}{p'}$ 的一个质因子，即 $p_n | \frac{n}{p'}$。所以，当 $i=\frac{n}{p'}$ 时，当 $prime[j]$ 枚举到 $p_n$，因为 $p_n | \frac{n}{p'}$，此时枚举终止，也就不会被 $p'$ 筛去。

这样，每个合数都只会被 `vis[i*prime[j]]=1` 标记一次，所有的数总共不会被标记超过 $n$ 次，所以线性筛的时间复杂度为 $O(n)$。

### *2.3.4 线性筛求积性函数

所有的积性函数都可以用线性筛来求。

举一个线性筛求 $d(n)$ 的例子。

既然是线性筛，就要从唯一分解和最小质因子的角度出发。

$d(1)=1$ 是显然的。

对于 $n>1$ 的情况，设 $P(n)$ 是 $n$ 的最小质因子，$K(n)$ 是 $n$ 最小质因子的指数，相当于把 $n$ 唯一分解后的 $p_1$ 和 $k_1$。

因为 $d(n)$ 是积性函数且 $\frac{n}{P(n)^{K(n)}}$ 与 $P(n)^{K(n)}$ 显然互质，所以 $d(n)= d(\frac{n}{P(n)^{K(n)}}) \times d(P(n)^{K(n)}) = d(\frac{n}{P(n)^{K(n)}}) \times (K(n)+1)$。

$P(n)$ 在线性筛时就能顺便求出来，所以考虑求 $K(n)$。

- 若 $P(n) \not = P(\frac{n}{P(n)})$，那就是没有多余的最小质因子，此时 $K(n)=1$。
- 若 $P(n) = P(\frac{n}{P(n)})$，这样也很简单，只要把指数加一继承一下就行了：$K(n) = K(\frac{n}{P(n)}) +1$。

知道这些就够用了。

求解代码：

```cpp
d[1]=d[0]=1;
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			prime[++tot]=i;
			P[i]=i,A[i]=1;
			d[i]=2; //素数i的d(i)=2;
		}
		else{
			//不是素数就按照前面的公式求d(i)
			if(P[i]!=P[i/P[i]]) A[i]=1;
			else A[i]=A[i/P[i]]+1;           
			d[i]=(A[i]+1)*d[i/pow(P[i],A[i])];
		}
		for(int j=1;j<=tot&&i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			P[i*prime[j]]=prime[j]; //线性筛原理，用最小质因子筛
			if(i%prime[j]==0) break;
		}
	}
```

# 3 欧拉函数与欧拉定理

## 3.1 欧拉函数

欧拉函数 $\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的数的个数，是积性函数。

### 3.1.1 求单个欧拉函数

假设要求 $\varphi(n)$，根据唯一分解定理，$n=\prod p_i^{k_i}$，$p_i$ 是质数，且 $k_i>0$。

那么根据欧拉函数积性性质 $\varphi(n)=\prod \varphi( p_i^{k_i} )$，考虑怎么求 $\varphi(p^{k})$。

可以发现，如果一个数与 $p^k$ 不互质，那么其一定是 $p$ 的倍数，所以和 $p^k$ 不互质的数的个数是 $\frac{p^k}{p} = p^{k-1}$，反过来就得到了 $\varphi(p^k)=p^k-p^{k-1} =p^k(1-\frac{1}{p})$。

那么
$$
\begin{aligned}
 \varphi(n) &= \prod \varphi(p_i^{k_i}) \\
 &= \prod p_i^{k_i}(1-\frac{1}{p_i}) \\
 &= n \prod (1-\frac{1}{p_i})
\end{aligned}
$$
这样就可以在 $O(\sqrt n)$ 的时间复杂度下求出 $\varphi(n)$：

```cpp
int tphi(int n) {
	int ans=n;
	for(int i=2;i*i<=n;++i)
		if(n%i==0){
			ans=ans/i*(i-1);    //乘上(1-1/p)
			while(n%i==0) n/=i; //把n中的i全部筛去
		}
	if(n!=1) ans=ans/n*(n-1);   //可能存在一个大于sqrt(n)的质因子
	return ans;
}
```
### 3.1.2 线性筛求多个欧拉函数

既然欧拉函数是积性函数，我们就能用线性筛来求 $1\sim n$ 的欧拉函数。

若 $i$ 是素数，那么 $\varphi(i)=i-1$。

若 $i$ 是合数，在线性筛中一个合数被筛去当且仅当被其最小质因数筛去，假设 $p_1$ 是 $i$ 的最小质因子，$k_1$ 是 $i$ 的最小质因子的指数，分类讨论：

1. $k_1 = 1$ 时，此时 $p_1$ 与 $\frac{i}{p_1}$ 互质，所以 $\varphi(i)=\varphi(\frac{i}{p_1}) \times \varphi(p_1) = \varphi(\frac{i}{p_1}) \times (p_1-1)$。
2. $k_1>1$ 时，此时 $p_1$ 与 $\frac{i}{p_1}$ 不互质，$\frac{i}{p_1}$ 的最小质因数仍然是 $p_1$，因为：

$$
\begin{aligned}
 \varphi(i) &= i \prod(1-\frac{1}{p_i}) \\
 \varphi(\frac{i}{p_1}) &= \frac{i}{p_1}\prod(1-\frac{1}{p_i})
\end{aligned}
$$
所以 $\varphi(i)= \varphi(\frac{i}{p_1}) \times p_1$。

```cpp
void sol(int n){
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!phi[i]) phi[i]=i-1,prime[++tot]=i; //i为素数
		for(int j=1;j<=tot&&i*prime[j]<=n;++j){
			if(i%prime[j]==0){                 //i为合数且k1>1
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else                              //i为合数且k1=1
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
```

### 3.1.3 欧拉函数的其他性质

一个最重要的就是：$n = \sum_{d|n} \varphi(d)$ 对任意正整数 $n$ 成立。

我们来证明这个，设集合 $A=\{1,2,\cdots,n \}$，并将该集合划分成若干个子集 $S_d=\{ k \in A \:| \: \gcd(k,n)=d\:\}$，显然任意两个 $S$ 的交集为空，且这些的并集等于 $A$，所以 $n = |A| = \sum |S_d|$，而且 $d|n$，故 $n =\sum_{d|n} |S_d|$。

那就考虑怎么求 $|S_d|$。

假设 $S_d$ 中一个元素为 $k$，有 $\gcd(k,n)=d$，设 $k=dm$，$m$ 是正整数，显然 $m$ 能取的数量就是 $|S_d|$。所以 $k=dm \le n$，$m \le \frac{n}{d}$。又 $\gcd(dm,n)=d$，$\gcd(m,\frac{n}{d})=1$。

令 $t=\frac{n}{d}$，所以 $1\le m\le t$ 且 $\gcd(m,t)=1$，$m$ 的取到的数量就是 $\varphi(t)=\varphi(\frac{n}{d})$，即 $|S_d|=\varphi(\frac{n}{d})$。$d|n$，所以 $\frac{n}{d}$ 是整数，且是 $n$ 的一个约数。

现在有了 $n=\sum_{d|n} \varphi(\frac{n}{d})$，发现在枚举 $d$ 时，$\frac{n}{d}$ 都是 $n$ 的正约数且成对，即 $d|n$ 时，$\frac{d}{n}|n$。因为对答案影响只有 $\varphi(\frac{n}{d})$，所以上述等式等价于 $n=\sum_{d|n} \varphi(d)$。得证。

~~不要问为什么最后证的这么牵强，这是我自己证的，能大概证出来就已经是我这个菜狗的极限了。~~

## 3.2 欧拉定理

欧拉定理和扩展欧拉定理常由于解决大指数化简的问题。

> 设 $a,n \in \mathbb{N}_+$，若 $a$ 与 $n$ 互质，则 $a^{\varphi(n)} \equiv 1 \pmod n$。

$n$ 为素数时，$\varphi(n)=n-1$，此时欧拉定理变成费马小定理。

那就考虑 $n$ 为其他数，设集合 $A$ 是所有与 $n$ 互质的正整数，即 $A=\{ x_1,x_2,\cdots , x_{\varphi(n)} \}$。

令集合 $B$ 为集合 $A$ 中每一个元素乘 $a$ 模 $n$ 构成的集合，即 $B=\{ ax_1 \bmod n,ax_2 \bmod n,\cdots , ax_{\varphi(n)} \bmod n\}$，那么 $A=B$。

首先证明 $B$ 中的每一个元素都互不相同：

若存在 $i \not= j,ax_i \equiv ax_j \pmod n$，那么 $a(x_i-x_j)\equiv 0 \pmod n$。因为 $a$ 与 $n$ 互质，$0 < x_i,x_j<n$ 且 $x_i\not= x_j$，故一定不存在一个 $(x_i-x_j)$ 使得 $a(x_i-x_j)\equiv 0 \pmod n$ 成立，得证。

因为 $x_i$ 与 $n$ 互质，$a$ 也与 $n$ 互质，所以 $ax_i$ 与 $n$ 互质。$A$ 包括了**所有**与 $n$ 互质的小于 $n$ 的正整数。所以每一个 $0 < ax_i \bmod n <n$ 都与 $A$ 中的一个元素对应，又 $|B|=|A|$ 且 $B$ 中每个元素互不相同，所以 $A=B$。

那么有：
$$
\begin{aligned}
 \prod_{i=1}^{\varphi(n)} ax_i &\equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n \\
 a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} x_i &\equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n \\
 a^{\varphi(n)} &\equiv 1 \pmod n
\end{aligned}
$$
得证欧拉定理。

## 3.3 扩展欧拉定理

> 设 $a,n \in \mathbb{N}_+$，有 $a^{2\varphi(n)} \equiv a^{\varphi(n)} \pmod n$。
>
> 等价地，对于任意的 $a,k,n \in \mathbb{N}_+$，若 $k \ge \varphi(n)$，那么有 $a^k \equiv a^{k \bmod \varphi(n) + \varphi(n)} \pmod n$。

证明：

~~咕咕咕~~。
 
# 4 二元线性不定方程

一般来说，形如方程 $ax+by=c$，其中 $a,b,c$ 是整数，求整数 $x,y$。通常使用裴蜀定理和扩展欧几里得算法来求解。与普通的欧几里得算法（辗转相除法）相似。

## 4.1 裴蜀定理

> 若 $a,b$ 不是全为 0 的整数，那么对于任意整数 $x,y$ 满足 $\gcd(a,b) \mid ax+by$，且存在整数 $x,y$，使得 $ax+by=\gcd(a,b)$。

下面是裴蜀定理的证明：

设集合 $S$ 为所有可以表示成 $ax+by$ 的数，即：
$$
S= \{ ax+by,x\in \mathbb{Z},y \in \mathbb{Z}\}
$$
设 $d$ 是集合 $S$ 中的最小正整数（$d=ax_0+by_0$），则有：

- $\forall w,w \in S$，则有 $d\mid w$。

证明：假设 $d \nmid w$，则存在 $x',y'$ 使得 $d \nmid ax'+by'$。由带余除法的定义可知：$ax'+by'=qd+r$，其中 $0 <r<d$。那么有：
$$
\begin{aligned}
r&=ax'+by'-qd \\
&=ax'+by'-q(ax_0+by_0) \\
&=a(x'-qx_0)+b(y'-qy_0)
\end{aligned}
$$
则 $r$ 是比 $d$ 更小，且在集合 $S$ 中的正整数。故假设不成立，证毕。

当 $x=1,y=0$ 时，$ax+by=a$。

当 $x=0,y=1$ 时，$ax+by=b$。

则有 $d\mid a$，$d \mid b$，所以 $d$ 是 $a,b$ 的公约数。

$\forall c$，$c$ 是 $a,b$ 的公约数。

则 $c\mid a,c\mid b$，那么有 $a=m_1c,b=m_2c$,可以得到:
$$
\begin{aligned}
d &= m_1cx_0+m_2cy_0 \\
 &= c(m_1x_0+m_2y_0)
\end{aligned}
$$
所以 $c\mid d$，$d$ 是 $a,b$ 的最大公约数，得证。

## 4.2 扩展欧几里得（exgcd）

> 已知整数 $a,b,c$，求二元方程 $ax+by=c$ 的整数解。

### 4.2.1 求特解

由裴蜀定理可知若 $\gcd(a,b) \nmid c$ 则无解，反之有解。即 $\gcd(a,b)$ 是 $c$ 的倍数。

那么只需要求 $ax+by=\gcd(a,b)$ 的一组解，然后把解同时乘以 $\frac{c}{\gcd(a,b)}$ 即可。

因为 $\gcd(a,b)=\gcd(b,a \bmod b)$。

所以 $bx_0+(a \bmod b)y_0= \gcd(b,a \bmod b)$。

如果重复上述操作可以得到：
$$
\begin{aligned}
a'x'+0y'&=\gcd(a',0)=a（①） \\
    x'=1&,y'=0
\end{aligned}
$$
考虑回代。

假设已经知道了 $bx_0+(a \bmod b)y_0=\gcd(b,a \bmod b)$ 的一组解，如何求 $ax+by=\gcd(a,b)$。

因为 $\gcd(a,b)=\gcd(b,a \bmod b)$，所以：
$$
\begin{aligned}
 ax+by  &= bx_0+(a \bmod b)y_0\\
   &= bx_0+(a-\left\lfloor\dfrac{a}{b}\right\rfloor b) y_0  \\
   &= bx_0+ay_0-\left\lfloor\dfrac{a}{b}\right\rfloor b y_0  \\
   &= ay_0+b(x_0-\left\lfloor\dfrac{a}{b}\right\rfloor y_0) \\

\end{aligned}
$$

即：
$$
 \begin{cases}
  x=y_0 \\
  y=x_0-\left\lfloor\dfrac{a}{b}\right\rfloor y_0
 \end{cases}
$$
这样就可以递归找出特解了。

注意式子 $①$，这里的 $y'$ 可不为 $0$，$y'$ 取其它整数虽导致得到的最终结果不同，但是符合题意的一组解，不影响答案。

求解代码：

```cpp
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1; y=0; //y可取其它整数
		return ;
	}
	exgcd(b,a%b,x,y);
	//得到上一组的解
	int tx=x;
	x=y;
	y=tx-a/b*y;
	//得到这一组的解
}
```

不要忘了最后的解要乘 $\frac{c}{\gcd(a,b)}$。

### 4.2.2 求通解

这个方程显然是有很多个解的，那么如何求所有的解。

现在已经求出了 $ax+by=c$ 的一组解，假设另一个解 $ax'+by'=c$。

两式子相减得：$a(x-x')+b(y-y')=0$。

令 $\Delta x=x-x',\Delta y=y-y'$，这个方程的的任何一个解与已经求出的特解的差 $(\Delta x,\Delta y)$，也一定满足 $(a\Delta x+ b \Delta y)=c$。

对于该方程的任意一组解 $(x'',y'')$，因为 $(ax''+by'')+(a\Delta x+ b \Delta y)=c+0=c$，故 $(x''+\Delta x,y''+\Delta y)$ 也是该方程的一组解。

因此只需求出 $a\Delta x+ b \Delta y=0$ 的所有解即可。

因为对于全部的解 $x$ 的绝对值越大，$y$ 的绝对值显然越大。

所以令方程 $ax+by=0$ 的一组非零解为 $(x_{\min},y_{\min})$，指 $x,y$ 的绝对值最小的一组解。

因为 $\left| ax\right|$ 是 $a$ 的倍数，$|by|$ 是 $b$ 的倍数，而且 $|ax|=|by|$。

所以 $|ax|$、$|by|$ 是 $a,b$ 的公倍数。

要让 $|ax|$ 最小，$|a|$ 是定值，就是让 $|x|$ 最小，即 $a,b$ 的最小公倍数 $ \operatorname{lcm}(a, b)=\frac{a\times b}{\gcd(a,b)}$。

因此最小的一组非零解就是 $(x_{\min},y_{\min}) = (\frac{b}{\gcd(a,b)},\frac{-a}{\gcd(a,b)}) $。

可以证明所有关于 $ax+by=0$ 的解都是 $(x_{\min},y_{\min})$ 的倍数。

令 $k \in \mathbb{Z}$，$(x,y)$ 是得到的特解，那么就得到了通解形式，即 $ax+by=c$ 的所有解：
$$
  \large(x+k\frac{b}{\gcd(a,b)} ,y-k\frac{a}{\gcd(a,b)}) 
$$

# 5 模意义下的乘法逆元

模意义下的乘法逆元简称“逆元”。

若存在一个整数 $x$，使得 $ax \equiv 1 \pmod p$，则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，即为 $a^{-1} \pmod p$。

## 5.1 逆元的求法

### 5.1.1 扩展欧几里得算法求逆元

$ax \equiv 1 \pmod p$ 可以拆成同余方程 $ax + py = 1$，求得的 $x$ 就是 $a$ 在模 $p$ 意义下的乘法逆元。

由裴蜀定理可以发现存在 $a$ 在模 $p$ 意义下的乘法逆元当且仅当 $a$ 与 $p$ 互素。

### 5.1.2 费马小定理求逆元

利用费马小定理 $a^{p-1} \equiv 1 \pmod p$，可以改写等式：$a^{p-1} = a \times a^{p-2} \equiv 1 \pmod p$，显然 $a^{p-2}$ 就是逆元。

但是费马小定理要求 $p$ 是质数且 $a$ 不能是 $p$ 的倍数，前者限制条件在扩展欧几里得里没有要求，所以用扩展欧几里得求逆元比费马小定理求逆元的实用性更广。

## 5.2 逆元的性质

**唯一存在性：**

由上文求逆元的方式可知存在 $a$ 在模 $p$ 意义下的乘法逆元只需要满足 $a$ 与 $p$ 互素，且 $ 0 < a^{-1} < p$，这个逆元是唯一确定的。

证明很简单：假设存在 $0 < x_1,x_2 <p$，$x_1<x_2$。那么 $ax_1 \equiv ax_2 \pmod p$，$a(x_2 - x_1) \equiv 0 \pmod p$。因为 $a$ 与 $p$ 互素，所以 $x_2 - x_1$ 是 $p$ 的倍数，但是 $0 < x_2-x_1<p$，不是 $p$ 的倍数。与前提假设矛盾，得证。

值得注意的是，逆元的 “唯一性”是指在模 $p$ 的意义下，如果只是根据定义来解那么是有很多解的，例如 $3^{-1}\equiv 5 \pmod 7$，$12$ 和 $19$ 也可以表示，与 $5 \pmod 7$ 等价。

其他相对来说没那么重要的性质：

**运算兼容性：**$(a \times b)^{-1} \equiv a^{-1} \times b^{-1} \pmod p$。

**互逆性：** 若 $0 <a,b <p$，$ab \equiv 1 \pmod p$，那么 $a$ 是 $b$ 在模 $p$ 意义下的乘法逆元，$b$ 也是 $a$ 在模 $p$ 意义下的乘法逆元。

## 5.3 逆元的作用

在进行模运算时有时会出现求 $\frac{a}{b} \bmod p$ 的情况，根据模运算的运算规律除法是不能直接模运算的，但是利用逆元 $b \times b^{-1} \equiv \pmod p$ 可以化成 $\frac{a}{b} \times b \times b^{-1} \equiv a \times b^{-1} \pmod p$ 这样乘的形式，就可以直接进行模运算了。

而且在处理 $ax \equiv b \pmod p$ 这样的方程时，两边同时乘 $a^{-1}$ 可以化简为 $x \equiv b \times a^{-1} \pmod p$。

在计算组合数 $C^{n}_{m} = \frac{m!}{n!(m-n)!}$ 时也可以利用逆元将分母转换为乘法。

## 5.4 *威尔逊定理

> 同余式 $(p-1)! \equiv -1 \pmod p$ 成立的充要条件是 $p$ 为素数。

必要性证明（$p$ 是素数 $\Rightarrow$ $(p-1)! \equiv -1 \pmod p$）：

设集合 $A=\{x \:| \: 1 \le x <p,x\in \mathbb{N} \}$。那么 $\forall d \in A$，$d$ 在模 $p$ 意义下的乘法逆元 $d^{-1}$ 显然存在，且根据逆元的唯一性，$d^{-1} \in A$。

由根据逆元的互逆性：
$$
 1 \times 2 \times 3 \times \cdots \times (p-1) = 1^{-1} \times 2^{-1} \times \cdots \times (p-1)^{-1} = (p-1)!
$$

因为 $p-1 \equiv -1 \pmod p$ 且 $p^{-1} = p$，又 $1 = 1^{-1}$，且剩下的元素能两两配对，故：
$$
1 \times 2 \times 2^{-1} \times \cdots \times (p-1) \equiv 1 \times 1 \times \cdots \times -1 \pmod p
$$
即：
$$
(p-1)! \equiv  -1 \pmod p
$$

------------

充分性证明（$(p-1)! \equiv -1 \pmod p$ $\Rightarrow$  $p$ 是素数）：

假设 $p$ 是合数，则存在一个整数 $1 < d < p$，使得 $d \: |\:p$。

显然有：$d \: | \: (p-1)!$，即 $(p-1)! \equiv 0 \pmod d$。

由已知条件：$(p-1)! \equiv 1 \pmod p$，由 $d$ 与 $p$ 的关系和上述同余式可以得到：
$$
0 \equiv -1 \pmod d
$$
显然 $d = \pm 1$，但是 $d>1$，故假设不成立，得证。

# 6 线性同余方程组

形如：
$$
 \begin{cases}
  x\equiv a_1 & \pmod {m_1} \\
  x\equiv a_2 & \pmod {m_2} \\
  x\equiv a_3 & \pmod {m_3} \\
        &\cdots\\
  x\equiv a_n & \pmod {m_n}
 \end{cases}
$$
的方程称为线性同余方程组，对于模数互质的特殊情况，可以用中国剩余定理（CRT）解决。

对于一般情况就只能使用扩展中国剩余定理（exCRT）解决。

## 6.1 中国剩余定理（CRT）

CRT 只能用来解决 $m_i$ 两两互质的情况。

令 $M= \prod m_i,M_i= \frac{M}{m_i}$。

显然 $M_i$ 与 $m_i$ 互质，则 $M_i$ 在模 $m_i$ 意义下的乘法逆元 $M_i^{-1}$ 存在。

即：$M_i \times M_i^{-1} \equiv 1 \pmod {m_i}$，$a_iM_i M_i^{-1} \equiv a_i \pmod {m_i}$。

对于 $j \ne i$，因为 $M_j=\prod_{i\ne j} m_i$，则 $M_j$ 是 $m_i$ 的倍数。

所以 $a_j M_j M_j^{-1} \equiv 0 \pmod {m_i}$。（注意，这里 $M_j^{-1}$ 是指模 $m_j$ 意义下的逆元，后面的也是。）

令 $x= \sum a_i M_i M_i^{-1}$。

$\forall i，$有：
$$
\begin{aligned}
 x &\equiv \sum a_i M_i M_i^{-1} \\
   &\equiv a_i M_i M_i^{-1} + \sum_{i \ne j} a_j M_j M_j^{-1} \\
   &\equiv a_i + \sum_{i \ne j} \: 0 \\
   &\equiv a_i \pmod {m_i}
\end{aligned}
$$
$x$ 就是方程的一个解。

1. 对于 $k \in \mathbb{Z}$，那么 $x+kM$ 也是该方程的解。

证明：$kM \equiv 0 \pmod {m_i},x + kM \equiv kM+\sum a_i M_i M_i^{-1} \equiv 0+a_i \equiv a_i \pmod {m_i}$。

2. 不存在其他解。

证明：假设存在另一个解 $x'$，显然满足 $x' \not\equiv x \pmod M$。

但是 $x' \equiv a_i \pmod {m_i},x \equiv a_i \pmod {m_i}$。

所以 $x' - x \equiv 0 \pmod {m_i}$ 对所有 $i$ 成立。

因为 $m_i$ 两两互质，所以 $\operatorname{lcm}(m_1,m_2,\cdots,m_n) = m_1 \times m_2 \times \dots \times m_n = M$。

故 $x'-x \equiv 0 \pmod M$，与前提假设矛盾。得证。

## 6.2 扩展中国剩余定理（exCRT）

把“$m_i$ 两两互质的条件”删除时，用 exCRT。

exCRT 本质上与 CRT 完全不同，CRT 的核心思想是利用逆元求解，这里没有了互质的条件，意味着核心思想变了。所以 exCRT 和 CRT 就是完全不同的两种算法，只是解决的问题相似而已。

如果方程组只有一个方程：$x \equiv a \pmod {m}$，那么该方程的最小非负整数解显然为 $a$。

如果只有两个方程 $\begin{cases} x \equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \end{cases}$，因为一个方程可以直接求出答案，所以考虑把这两个方程合并成一个方程：

把同余式改写成等式：$x=a_1+k_1m_1=a_2+k_2m_2$。

移项：$k_1m_1-k_2m_2=a_2-a_1$。

这刚好是一个二元方程，可以用 exgcd 求解 $k_1$。

注意，根据裴蜀定理，若 $\gcd(m_1,m_2) \nmid (a_2-a_1)$ 则无解。

求解出 $k_1$ 后，可以得到一个特解 $x'=a_1+k_1m_1$。

现在已经得到了特解，那么 $\begin{cases} x \equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \end{cases}$ 的通解为 $x'+k \times \operatorname{lcm} (m_1,m_2)$，其中 $k\in \mathbb{Z}$ 。

这很显然，$\operatorname{lcm} (m_1,m_2)$ 同时是 $m_1$ 和 $m_2$ 的倍数，故 $\begin{cases} x + k \times \operatorname{lcm} (m_1,m_2)\equiv a_1 +0\pmod {m_1} \\ x+ k \times \operatorname{lcm} (m_1,m_2)\equiv a_2 +0\pmod {m_2} \end{cases}$。

我们令 $x_0$ 是通解中的最小非负整数，那么原来的两个方程可以合并为：
$$
x \equiv x_0 \pmod {\operatorname{lcm} (m_1,m_2)}
$$

这里的 $x_0$ 显然小于 $\operatorname{lcm} (m_1,m_2)$，并且没有其他大于等于零小于 $\operatorname{lcm} (m_1,m_2)$ 的整数解，这里由通解就能直接看出来，不再证明。

合并方程就是 exCRT 的核心操作，如此反复执行合并操作，就可以把原来的 $n$ 个方程合并成一个方程，进而得到解。

[洛谷P4777](https://www.luogu.com.cn/problem/P4777)核心代码：

```cpp
signed main(){
	int n,a1,b1,a2,b2; scanf("%lld%lld%lld",&n,&a1,&b1);
	for(int i=1;i<n;++i){
		//a1,a2是上一组方程
		scanf("%lld%lld",&a2,&b2);
		int k1,k2;
		int d=exgcd(a1,a2,k1,k2);
		int bg=a2/d; //k1的特解形式
		//判断无解
		if((b2-b1)%d!=0) return !printf("Impossbile\n");
		k1=(mul(k1,(b2-b1)/d,bg));//求出一种解
		//相当于k1=(k1*(b2-b1)/d%bg)，这里用了龟速乘
		
		//更新新的方程
		b1=k1*a1+b1;
		a1=a1*bg;
		b1=(b1%a1+a1)%a1;//求出最小非负的b1
	}
	printf("%lld\n",b1);
}
}
```

# 7 组合数学与计数

[这一部分可详见我的题解](https://www.luogu.com.cn/article/73uisgf1)。

## 7.1 二项式定理

> 若 $n$ 是正整数，则有：$\begin{aligned} (x+y)^n = \sum_{i=0}^n C_{n}^{i} x^i y^{n-i} \end{aligned}$。

用数学归纳法证明：

当 $n=1$ 时原式显然成立。

假设 $n=k$ 时原式成立，则 $n=k+1$ 时，有：
$$
\begin{aligned}
 (x+y)^{k+1} &= (x+y)(x+y)^k \\
  &=(x+y) \sum_{i=0}^{k}C_{k}^{i} x^i y^{k-i} \\
  &=(x+y) (C_k^0 y^k+C_k^1 x y^{k-1}+\dots+C_k^{k-1}x^{k-1}y+C_k^k x^k) \\
  &=x^{k+1} + y^{k+1} + (C_k^0+C_k^1)xy^k+(C_k^1+C_k^2)x^2y^{k-1}+\dots+(C_k^{k-1}+C_k^k)x^ky \\
  &= x^{k+1} + y^{k+1} + \sum_{i=1}^k (C_k^{i-1}+C_k^{i})x^i y^{k-i+1}
\end{aligned}
$$
因为
$$
\begin{aligned}
C_k^{i-1}+C_k^{i} &= \frac{k!}{(i-1)!(k-i+1)!} +\frac{k!}{i!(k-i)!} \\
&= \frac{k!\:i!\:(k-i)!+k!\:(i-1)!\:(k-i+1)!}{i! \: (i-1)! \: (k-i)! \: (k-i+1)!} \\
&= \frac{(k+1)!}{i! (k-i+1)!} \\
&= C_{k+1}^i
\end{aligned}
$$
所以
$$
\begin{aligned}
(x+y)^{k+1} &= x^{k+1} + y^{k+1} + \sum_{i=1}^k C_{k+1}^ix^i y^{k-i+1} \\
&=\sum_{i=0}^{k+1}C_{k+1}^ix^i y^{k-i+1}
\end{aligned}
$$
因此 $n=k+1$ 时原式也成立，得证。

## 7.2 卢卡斯定理（Lucas 定理）

一个引理：若 $p$ 是素数，则有：$(x+y)^p \equiv x^p + y^p \pmod p$。

证明：由二项式定理可知：$\begin{aligned} (x+y)^p = \sum_{i=0}^p C_{p}^{i} x^i y^{p-i} \end{aligned}$。

其中当 $1 \le i < p$ 时：
$$
\begin{aligned}
C_p^i &= \frac{p!}{i!(p-i)!} \\
&= \frac{p\times(p-1)!}{i \times (i-1)!(p-i)!} \\
&= \frac{p}{i} C_{p-1}^{i-1}
\end{aligned}
$$
所以
$$
\begin{aligned}
C_p^i & \equiv \frac{p}{i} C_{p-1}^{i-1} \\
& \equiv p \times i^{-1} C_{p-1}^{i-1} \\
& \equiv 0 \pmod p
\end{aligned}
$$
其中 $i^{-1}$ 表示 $i$ 在模 $p$ 意义下的乘法逆元。

原式只剩下 $i=0,p$ 两项，得证。

---

Lucas 定理：

> 若 $p$ 是素数，则有：$C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p $。

证明：

根据带余除法，令 $n=ap+b,m=cp+d$，其中 $0 \le b,d < p$。

根据二项式定理得到式子一：
$$
(1+x) ^n \equiv \sum_{i=0}^{n} C_n^i x^i \pmod p
$$
根据二项式定理和引理得到式子二：
$$
\begin{aligned}
 (1+x) ^n &\equiv (1+x)^{ap+b} \\
 &\equiv ((1+x)^p)^a\times(1+x)^b\\
 &\equiv (1+x^p)^a \times(1+x)^b \\
 &\equiv (\sum_{i=0}^a C_a^i x^{ip})(\sum_{j=0}^b C_b^j x^j) \pmod p
\end{aligned}
$$
由式子一可知 $x^m$ 的系数为 $C_n^m$。

由式子二可知 $x^m=x^{cp+d}$ 的系数为 $C_a^c C_b^d$。

因为 $\lfloor \frac{n}{p} \rfloor = a ,\lfloor \frac{m}{p} \rfloor = c,n \bmod p =b,m \bmod p=d$。

所以 $C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p$，证毕。

在求解时，根据费马小定理：$(m!)^{p-1} \equiv 1 \pmod p,[(n-m)!]^{p-1} \pmod p$。

那么有：
$$
C_n^m=\frac{n!}{m!(n-m)!} \equiv n! \times m!^{p-2} \times (n-m)!^{p-2} \pmod p
$$

这样就可以求解了。

# 参考资料

大致是按参考程度排列的。

- 《深入浅出程序设计竞赛（进阶篇）》高等教育出版社，编著：汪楚奇。
- [同余代数](https://www.luogu.com.cn/article/v12gqxap)——Alex_Wei。
- [基础数论笔记](https://www.luogu.com.cn/article/fggjf8sy)——Tomwsc。
- [OI Wiki-数论](https://oi-wiki.org/math/number-theory/basic/)。
- 《数论：概念与问题》哈尔滨工业大学出版社，编著：[美]Titu Andreescu。
- [扩展中国剩余定理](https://www.luogu.com.cn/article/lr8vtpzl)——阮行止。

正在渲染内容...