Maths

chifan-duck / 2023-08-11 / 原文

逻辑，集合与计数

逻辑

有命题 $p,q$ 和一个复合命题 “若 $p$，则 $q$”。若复合命题为真，则称 $p\Rightarrow q$。
若 $p\Rightarrow q$，则称 $p$ 是 $q$ 的 充分条件，$q$ 是 $p$ 的 必要条件。若 $p\Rightarrow q,q\Rightarrow p$ 均为真，则称 $p$ 和 $q$ 互为 充要条件，可记作 $p\Leftrightarrow q$。或称 $p$ 等价于 $q$。
若 $p\Rightarrow q$，则 $\neg p\Rightarrow\neg q$。反之亦然。即原命题与其 逆否命题 同真同假。
对于任意的 $M$ 中的 $x$，有 $p(x)$ 成立，则可记作 $\forall x\in M,p(x)$。
存在 $M$ 中的 $x$，有 $p(x)$ 成立，则可记作 $\exists x\in M,p(x)$。
$\forall x\in M,p(x)$ 的否定形式为 $\exists x\in M,\neg p(x)$。
$\exists x\in M,p(x)$ 的否定形式为 $\forall x\in M,\neg p(x)$。

集合

集合之间的并 $A\cup B=\{x|x\in A \vee x \in B\}$。
集合之间的交 $A\cap B=\{x | x\in A\wedge x\in B\}$。
集合之间的补 $\complement_U A=\{x|x\in U \wedge x\not\in A\}$。
集合之间的乘法 $A\times B=\{(a,b) | a\in A \wedge b \in B\}$。性质：$|A\times B|=|A| \times |B|$。
集合的乘方运算 $A^{k}=\{(x_1,x_2,\cdots,x_k) | \forall 1\leq i\leq k,x_i\in A\}$。性质：$|A^{k}|=|A|^{k}$。
集合以 $2$ 为底的幂 $2^{A}=\{a|a \subseteq A\}$。性质 $|2^{A}|=2^{|A|}$。
集合间的关系（一）子集：若 $A\subseteq B$，等价于 $\forall i\in A,i\in B$.
集合间的关系（二）真子集：若 $A\subset B$，等价于 $A\subseteq B \wedge \complement_B A \neq \varnothing$。
集合之间的关系（三）相等：若 $A=B$，等价于 $A\subseteq B \wedge A\not\subset B$。
集合运算的分配律：$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$；$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$。
集合运算中，并集和交集满足结合律和交换律。
$\complement_U (A\cup B)=\complement_U A\cap \complement_U B$。$\complement_U (A\cap B)=\complement_U A\cup \complement_U B$。

容斥原理

\[|\bigcup_{i=1}^{n} A_i|=\sum_{k=1}^{n}(-1)^{k+1}\sum_{1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq n} |\bigcap_{j=1}^{k}A_{i_j}| \]

映射

对于 $A,B$ 两个非空集合，若存在某种对应关系 $f$，使得对于任意的 $x\in A$，在 $B$ 中有一个唯一的集合与之对应。则称 $f:A\to B$ 为 $A$ 到 $B$ 的一个映射。
$f:A\to B$ 中，$A$ 是定义域，$f(x)=\{f(x)|x\in A\}$ 是像集合。
$f:A\to B$ 中，满足 $f(x)=B$ 的映射是满射。满足 $\forall x_1,x_2\in A,x_1\neq x_2$ $f(x_1)\neq f(x_2)$ 的映射是单射。同时满足满射和单射的条件的是一一映射。
对于一一映射 $f:A\to B$，则 $\forall x\in A,f^{-1}(f(x))=x \wedge \forall y\in B,f(f^{-1}(y))=y$。

映射的构造

构造一一映射 $f:$ 整数集 $\to$ 偶数集。

$n\to 2n$

构造一一映射 $f:\mathbb{Z}^{+}\to\mathbb{Z}$。

$n\to (-1)^{n}\lfloor\frac{n}{2}\rfloor$

构造一一映射 $f:\mathbb{Z}^{+}\to\mathbb{Q}$。

由于 $\forall x\in\mathbb{Q},\exists (p,q)$，使的 $\gcd(p,q)=1,\frac{p}{q}=x$。令 $\frac{0}{0}=0$。

于是我们可以将所有形如 $(p,q)$ 的数对看出二维坐标。先将 $\mathbb{Q}$ 转为 $\mathbb{Q}^{+}$，可以从 $(0,0)$ 开始斜着遍历所有二维坐标，然后每个 $\frac{p}{q}$ 可以映射到遍历次序。

不存在一一映射 $f:\mathbb{Z^{+}}\to\mathbb{R}$。

证明：假定我们已经存在了这样一个 $f$。我们构造一个数列 $\{f(x)\}$，然后构造 $a=\overline{0.b_1b_2b_3\cdots}$，其中 $b_k$ 与 $f(k)$ 第 $k$ 位不同。则不存在 $x\in\mathbb{Z}^{+},f(x)=a$。不满足满射性质。

组合计数

排列组合定义：$A_{n}^{k}=\frac{n!}{(n-k)!},C_{n}^{k}=\binom{n}{k}=\frac{A_{n}^{k}}{k!}=\frac{n!}{k!(n-k)!}$。
一些组合恒等式：

\[\begin{aligned} &\binom{n}{k}=\binom{n}{n-k}&(1)\\ &\sum_{i=0}^{n}\binom{n}{i}=2^n&(2)\\ &\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2i}=\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n}{2i+1}&(3)\\ &\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}&(4)\\ &\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\frac{n-k+1}{k}\binom{n}{k-1}&(5)\\ \end{aligned} \]

证明一下第三个和第四个。

第三个：
第四个：考虑固定一个特殊物品，然后选这个物品 $\binom{n-1}{k-1}$ 或不选这个物品 $\binom{n-1}{k}$。

归纳与递归

求和性质

重命名性质（与下标无关）
累加性质
线性性质
交换顺序性质

柯西极限理论

数列 ${x_m}$ 收敛的充要条件是：

对于给定的正数 $\epsilon$ 总是存在正整数 $N$ 对于 $\forall n,m > N$ 满足 $|x_n - x_m| < \epsilon$。

对于函数与数项结论类似。

Abel 恒等式

\[\sum_{i=1}^{n}a_i b_i = S_{n} b_{n} + \sum_{i=1}^{n-1} S_i(b_{i+1}-b{i}) \]

Proof：$\sum_{i=1}^{n}a_i b_i = \sum_{i=1}^{n}(S_{i+1}-S_{i}) b_i = S_{n} b_{n} + \sum_{i=1}^{n-1} S_i(b_{i+1}-b{i})$。

实质上是离散情况下的分部积分。

数学归纳法

我们定义 $f(x)$ 代表一个命题，$f(x) = 0$ 代表其不成立，否则成立。

第一类数学归纳法：

若 $f(1) = 1$ 且对于 $\forall k$ 满足 $f(k) = 1 $ 有 $ f(k+1) = 1$ 则对于任意正整数 $N$ 有 $f(N) = 1$。

第二类数学归纳法：

若 $f(1) = 1$ 且对于 $\forall k$ 有 $\forall i < k $ 满足 $ f(i) = 1$ 有 $f(k) = 1$ 则对于任意正整数 $N$ 有 $f(N) = 1$。

天平问题

错位排列

$D_n$ 表示随机生成一个长度为 $n$ 排列 $A$，满足 $\forall 1 \leq i \leq n,A_i\neq B_i$ 的长度为 $n$ 的排列 $B$ 的数量。
$D_n$ 的通项公式：

\[\begin{aligned} &D_n\\ &=\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}(n-i)!\\ &=\sum_{i=0}^{n}(-1)^{i}\frac{n!}{i!(n-i)!}(n-i)!\\ &=n!\sum_{i=0}^{n}(-1)^{i}\frac{1}{i!} \end{aligned} \]

对于第一步，由于 $n!=\sum_{i=0}^{n}\binom{n}{i}D_{n-i}=\sum_{i=0}^{n}\binom{n}{i}D_i$，所以可以用二项式反演得到。什么容斥不存在的。

$D_n=\text{round}\left(\dfrac{n!}{e}\right)$。其中 $\text{round}(x)$ 表示 $x$ 四舍五入到个位后的值。

将 $f(x)=e^{x}$ Maclaurin 展开（在 $0$ 处的 Taylor 展开），得：

\[f(x)=\sum_{i=0}^{\infty}\dfrac{x^{i}}{i!} \]

取 $x=-1$，得 $e^{-1}$ 的级数形式：

\[\sum_{i=0}^{\infty}(-1)^i\frac{1}{i!} \]

下面证明误差 $\leq 0.5$

\[\begin{aligned} &(n!)e^{-1}-D_n\\ &=n!\left(\sum_{i=0}^{\infty}(-1)^{i!}\frac{1}{i}-\sum_{i=0}^{n}(-1)^{i}\frac{1}{i!}\right)\\ &=n!\sum_{i=n+1}^{\infty}(-1)^{i}\frac{1}{i!}\\ &=\sum_{i=n+1}^{\infty}(-1)^{i}\frac{n!}{i!} \end{aligned} \]

通过 Wolfram Alpha 可得上式绝对值 $\leq 0.5$ 则 $n\gt -2$。满足 $n\in\mathbb{N}$ 成立。

当然，这个结论也可以通过计算这个展开的拉格朗日余项得到。

$D_n$ 的递推公式：$D_n=(n-1)(D_{n-1}+D_{n-2})$。

Catalan 数

Catalan 数 $C_n$ 是下面这些问题的答案：

在 $n\times n$ 的网格纸上从左下角到右上角的不经过左下——右上对角线的最短路径数量。

常见的等价问题：

A 和 B 进行 $2n$ 轮比赛，使的最终平手且 A 的比分从未超过 B 的合法每场比赛胜负情况的总状态的数量。

满足 $\forall 1 \leq i \leq 2n,a_i=\pm 1,\sum_{k=1}^{i}a_k\geq 0$ 的长度为 $2n$ 的序列 $a$ 的数量。

常见的等价问题：

满足所有右括号均被匹配的长度为 $2n$ 的括号数量。
一个进栈序列为 $1,2,3,\cdots,n$ 的栈的出栈序列数量。
有 $2n$ 个人买票，每人一张钞票，入场费 $x$ 元。初始时售票处没有钞票。有 $n$ 个人有面值为 $x$ 的钞票，其他人有面值为 $2x$ 的钞票。求有多少种安排买票顺序的方法，使的如果需要找零都可以找出来？

$n$ 个结点可构造的不同的二叉树数目。

对角线不相交的情况下，将一个凸 $n$ 边形区域分成三角形区域的方法数。

在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数。

Catalan 数的递推公式：$C_0=C_1=1,C_n=\sum_{i=1}^{n}C_{i-1}C_{n-i}$
Catalan 数的通项公式：$C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}$

通项公式推导方法：首先考虑 $(0,0)$ 到 $(x,y)$ 的路径总数为 $\binom{x+y}{x}$。

然后考虑 $(0,0)$ 到 $(n,n)$ 的路径数，可以考虑过了对角线的路径数，将这些路径对 $y=x-1$ 作一个对称，则对称到了 $(n-1,n+1)$，路径数为 $\binom{2n}{n-1}$。最后用总路径数 $\binom{2n}{n}$ 减去它。

递推公式转通项公式

累加形式：

\[a_n = a_{n-1} + f(n) \]

有通项公式：

\[a_{n} = a_0 + \sum_{i=1}^{n} f(i) \]

累乘形式：

\[a_n = k \times a_{n-1} + f(n) \]

解法：

\[\frac{a_n}{k^n} = \frac{a_{n-1}}{k^{n-1}} + \frac{f(n)}{k^n} \]

令 $b_n = \frac{a_n}{k^n},f(n) = \frac{f(n)}{k^n}$ 则转化为累加形式求解即可。

Fib 形式：

\[a_n = p \times a_{n-1} + q \times a_{n-2} \]

假若 $p^2 = 4 \times q$ 有以下解法：

\[a_n = 2 \times k a_{n-1} + k^2 \times a_{n-2} \]

\[a_n - k \times a_{n-1} = k a_{n-1} + k^2 \times a_{n-2} \]

令 $b_{n} = a_n - k \times a_{n-1}$ 则转化为累乘形式。

通用形式：

Stirling 数与 Bell 数

差分的性质：对于某一个 $k$ 次多项式，则有：

\[f_n=\sum_{i=0}^{k}\binom{n}{i}(\Delta^{i}f)_0 \]

其中 $\Delta^{i}f$ 表示 $f$ 的 $i$ 阶差分。即 $\Delta^{0}f=f,(\Delta^{k+1}f)_{p}=(\Delta^{k}f)_{p+1}-(\Delta^{k}f)_{p}$。

定义第二类 Stirling 数 $\left\{ \begin{matrix} 0 \\ 0 \end{matrix} \right\}=1$，$\left\{ \begin{matrix} n \\ i \end{matrix} \right\}=\dfrac{1}{i!}(\Delta^{i}n^{p})_0$。即：

\[n^{p}=\sum_{i=0}^{p}\left\{ \begin{matrix} p \\ i \end{matrix} \right\}A_{n}^{i}=\sum_{i=0}^{p}\left\{ \begin{matrix} p \\ i \end{matrix} \right\}\binom{n}{i}i! \]

第二类 Stiring 数的递推公式 $\left\{ \begin{matrix} p \\ i \end{matrix} \right\}=\left\{ \begin{matrix} p-1 \\ i-1 \end{matrix} \right\}+i\times\left\{ \begin{matrix} p-1 \\ i \end{matrix} \right\}$。

Proof：有兴趣自己去证。

第二类 Stiring 数的组合意义：将 $p$ 个有标号小球放进 $i$ 个无标号篮子的方案数为 $\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}}\str{p}{i}$。
递推式的组合证明：要么放进一个新篮子 $\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}}\str{p-1}{i-1}$、要么放进原来的篮子 $\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}}\str{p-1}{i}$ 但篮子有 $i$ 个所以要乘以 $i$。
第二类 Stiring 的另一个组合意义：$p$ 元集到 $i$ 元集的满射数量为 $\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}}\str{p}{i}$。

所以可以使用容斥得到第二类 Stiring 数的一个通项公式：

\[\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}} \str{p}{i}=\dfrac{1}{i!}\sum_{k=0}^{i}(-1)^{k}\binom{p}{k}(i-k)^{p} \]

也可以用差分的那个式子二项式反演得到。

定义将 $p$ 个元素分成若干个部分的方案数为 Bell 数 $B_p$，则：

\[\newcommand\str[2]{\left\{ \begin{matrix} #1 \\ #2 \end{matrix} \right\}} B_n=\sum_{i=0}^{n}\str{p}{i} \]

Bell 数有递推公式：

\[B_p=\sum_{i=0}^{p-1}\binom{p-1}{i}B_{p-i-1} \]

枚举有多少个元素与第 $p$ 个元素在一起，然后剩下的套用 Bell 数。

对于排列数的展开：

\[p!\binom{n}{p}=A_{n}^{p}=\sum_{i=1}^{p}(-1)^{p-i}\begin{bmatrix}p\\ i\end{bmatrix}n^{i} \]

其中 $\begin{bmatrix}p\\ i\end{bmatrix}$ 为第一类 Stirling 数。

第一类 Stirling 数的递推公式：

\[\newcommand\str[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \str{n}{0}=[n=0],\str{n}{k}=\str{n-1}{k-1}+(n-1)\str{n-1}{k} \]

组合意义：将 $n$ 个元素划分为 $i$ 个圆排列的方案数为 $\newcommand\str[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}\str{n}{i}$。

数论

整除

整除定义：若 $a|b$，则 $\exists n \in \mathbb{Z},b=an$。
整除的传递性：$a|b,b|c \Rightarrow a|c$。

Proof：$\exists n,m \in \mathbb{Z},b=na,c=mb$，则 $c=nma$。

整除的可加减性 $c|a,c|b\Rightarrow c|(a\pm b)$。

Proof：$\exists n,m\in\mathbb{Z},a=nc,b=mc$，则 $a+b=(n+m)c$。

整除的可乘性 $a|b,c|d\Rightarrow ac|bd$。

Proof：$\exists n,m\in\mathbb{Z},b=na,d=mc$，则 $bd=nm(ac)$。

证明：$3|x,7|x\Rightarrow 21|x$。

\[\begin{aligned}&\because 3|x,7|x\\&\therefore 21|7x,21|3x\\&\therefore 21|(7x-3x-3x)\\&\therefore 21|x\end{aligned} \]

gcd & lcm

最大公约数 $\gcd(a,b)=\max\{m|,m|a\wedge m|b\}$。
最小公倍数 $\text{lcm}(a,b)=\min\{n|a|n\wedge b|n,n\in\mathbb{Z}^{+}\}$。
带余除法 $\forall a,b\in\mathbb{Z}^{+},\exists q,r\in\mathbb{Z}$，使得：

\[\begin{cases} a=bq+r\\ 0\leq r \leq b-1 \end{cases} \]

带余除法满足存在性和唯一性。

$a|n,b|n\Rightarrow \text{lcm}(a,b)|n$

Proof: 设 $n\div \text{lcm}(a,b)=q\cdots r$。则 $n=q\text{lcm}(a,b)+r$。又因为 $q\text{lcm}(a,b)|a,q\text{lcm}(a,b)|b$，则 $r|a,r|b$。又因为 $0\leq r\lt \text{lcm}(a,b)$。所以 $r=0$，所以 $\text{lcm(a,b)}|n$。

$\gcd(a,b)=\gcd(a-b,b)$

Proof：令 $A=\{m|m|a,m|b\},B=\{m|m|(a-b),m|b\}$。则 $\forall x\in A,x|a,x|b$，则 $x|a-b$。则 $x\in B$。$\forall x\in B,x|(a-b),x|b$，则 $x|a$。所以 $A=B$。所以 $\max\{x|x\in A\}=\max\{x|x\in B\}$，即 $\gcd(a,b)=\gcd(a-b,b)$。

若 $a\div b=q\cdots r$，则 $\gcd(a,b)=\gcd(b,r)$。

Proof：$\gcd(a,b)=\gcd(a-bq,b)=\gcd(r,b)=\gcd(b,r)$。

辗转相除法：

function GCD(a,b)
	if b == 0 then return a
	else then return GCD(b,a mod b)
end

裴蜀定理：关于 $x,y$ 的不定方程 $ax+by=\gcd(a,b)$ 一定有解。证明方法，下面的 ExGCD。
ExGCD: 解方程 $ax+by=\gcd(a,b)$ 的一般方法。例如：$55x+23y=1$。

先模拟辗转相除法：

\[\begin{aligned} &55\div23=2\cdots9\\ &23\div9=2\cdots5\\ &9\div5=1\cdots4\\ &5\div4=1\cdots1\\ &4\div1=4\cdots0\\ \end{aligned} \]

然后逆推：

\[\begin{aligned} &\gcd(a,b)=1\\ &=5-4\times 1=5-4\\ &=5-(9-5\times 1)=2 \times 5-9\\ &=2\times(23-2\times 9)-9=2\times23-5\times9\\ &=2\times23-5\times(55-2\times3)=12\times23-5\times55 \end{aligned} \]

得出 $x=-5,y=12$。

$k|a,k|b \Rightarrow k|\gcd(a,b)$
$a|n,b|n\Rightarrow ab|n$
$a|bc,\gcd(a,b)=1\Rightarrow a|c$
$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$
$\gcd(a,b)=\gcd(a,b,ax)$
$\gcd(a,b,c)=\gcd(\gcd(a,b),\gcd(a,c))$

算术基本定理

质数的不可约数定义：若 $p\geq 2$，且 $\{x| x|p,x\in\mathbb{Z}^{+}\}=\{1,p\}$。则称 $p$ 是一个质数。全体质数集合为 $\mathbb{P}$。
存在无限多个质数。

Proof: 若有有限多个质数，设其为 $p_1,p_2,\cdots,p_n$。则令 $A=p_1p_2\cdots p_{n-1}p_n+1$。则 $A$ 不是质数，且存在一质因子 $p|A$。则 $\forall 1\leq i \leq n,p\neq p_i$。矛盾。

$2^{n}-1\in\mathbb{P}\Rightarrow n\in\mathbb{P}$
$p\in\mathbb{P},p\not\mid a\Rightarrow \gcd(a,p)=1$
$p\in\mathbb{P},p|a,b\Rightarrow p|a \lor p|b$
算术基本定理：任何一个大于 $1$ 的正整数 $n$ 均可分解成若干个质数的乘积。这种分解方法是唯一的。

Proof：先证明可分解：

当 $n=2$ 时可分解。
若 $n=2,3,\cdots,k$ 时均可分解，则 $n=k+1$ 时，若 $k+1\in\mathbb{P}$，则满足条件。若 $k+1\not\in\mathbb{P}$，则 $\exists a,b\in\mathbb{Z}^{+}\land 2\leq a,b \leq k\land ab=k+1$，又因为 $a,b$ 可分解，所以 $k+1$ 亦可分解。

再证明唯一性：

若 $n=\prod_{i=1}^{s}p_i=\prod_{i=1}^{t}q_i,\forall 1 \leq i \leq s,p_i\in\mathbb{P},\forall 1 \leq i \leq t,q_i \in \mathbb{P}$ 且钦定 $s\geq t$。
则 $p_1|\prod_{i=1}^{t}q_i$，钦定 $p_1|q_1$。又因为 $p_1>1$，所以 $p_1=q_1$，约去。以此类推。
定义 $v_p(n)$ 表示 $n$ 的标准分解形式中所含质因子 $p$ 的指数。
$v_p(ab)=v_p(a)+v_p(b)$。
Proof: 取 $a$ 标准分解 $p^{v_p(a)}\cdots$，$b$ 标准分解 $p^{v_p(b)}\cdots$，$ab$ 标准分解 $p^{v_p(a)v_p(b)}\cdots$ 且省略号表示的东西一定与 $p$ 互质。
$v_p(\gcd(a,b))=\min(v_p(a),v_p(b))$
$v_p(a)\neq v_p(b)\Rightarrow v_p(a+b)=\min(v_p(a),v_p(b))$
Proof: 提取公因数。
$v_p(n!)=\sum\limits_{i=1}^{\infty}\lfloor\dfrac{n}{p^i}\rfloor$
Proof: 对于 $n$ 以内的所有包含 $p^i$ 因子数挨个贡献一次，每个 $v_p(n)=k$ 的 $n$ 会被正好贡献 $k$ 次。

同余

剩余系与欧拉函数

对于一个集合 $S$，若其满足大小为 $n$ 且 $\forall i \in \mathbb{N},\exists j\in S$，使得 $j\equiv i\pmod{n}$。则称 $S$ 为模 $n$ 的完全剩余系。简称完系。
对于模 $n$ 的完系 $S$，其乘上一个与 $n$ 互质的数 $a$，亦是完系。
对于一个模 $n$ 的完全剩余系的一个子集 $S$，使得 $\forall i\in S$，使得 $\gcd(i\bmod n,n)=1$。满足这个条件的极大 $S$ 为模 $n$ 的既约剩余系。简称缩系。
定义欧拉函数 $\varphi(x)=\sum_{i=0}^{x-1}[\gcd(i,x)=1]$。
模 $n$ 的缩系大小为 $\varphi(n)$。
欧拉函数是积性函数。

Proof: 下证 $\gcd(n,m)=1\Rightarrow \varphi(nm)=\varphi(n)\varphi(m)$

设模 $n$ 的缩系 $S$，模 $m$ 的缩系 $T$。

构造 $G=\{ni+mj|i\in T,j\in S\}$。则满足 $\forall i\in G$ 满足 $\gcd(i,nm)=1$。且 $G=\varphi(n)\varphi(m)$。且两两不同余。所以 $G$ 为模 $nm$ 缩系。

若 $ab\equiv 1\pmod{n}$，则称 $b$ 为 $a$ 模 $n$ 意义下的逆元。记作 $b=a^{-1}$。
若 $\gcd(a,n)=1$，则模 $n$ 的意义 $a^{-1}$ 存在且唯一。
Proof: 构造 $S=\{x|x\in\mathbb{N},x\lt n\}$ 为 $n$ 的完系，则乘上 $a$ 后 $S^{'}=\{ax|x\in \mathbb{N},x<n\}$ 亦为完系。所以存在唯一的一个 $a^{-1}$（在 $S^{'}$ 中找）。
若 $\gcd(a,n)\neq 1$，则 $a$ 不存在模 $n$ 意义下的逆元。
推论：若 $p\in\mathbb{P}$，则 $1\sim p-1$ 均存在逆元。也就是说模 $p$ 缩系四则运算封闭。
欧拉函数的公式：
先得出：

\[\varphi(p^{k})=p^{k}-\dfrac{p^{k}}{p}=p^{k}(1-\dfrac{1}{p}),p\in\mathbb{P},k\in\mathbb{Z}^{+} \]

然后计算 $\varphi(n)$ 可以将 $n$ 分解。所以得：

\[\varphi(n)=n\cdot\sum_{p\in\mathbb{P},p|n}\left(1-\dfrac{1}{p}\right) \]

若 $p\in\mathbb{P},p\equiv1\pmod{2}$， $\sum_{i=1}^{p-1}\frac{1}{i}=\frac{m}{n}$，且 $\gcd(m,n)=1$，证明 $p|m$。
$(p-1)!(1+\frac{1}{2}+\cdots+\frac{1}{p-1})=\frac{(p-1)!}{n}m$。令前系数为 $k$，则等于 $(p-1)!\sum_{i=1}^{p-1}i^{-1}\equiv (p-1)!(1+2+\cdots+(p-1))\equiv 0\pmod{p}$。

求逆元的方法：
1. ExGCD。相当于解 $ax+yn=1$ 中的 $a^{-1}=x$。此方法亦可证逆元存在性唯一性和不互质不存在性。
1. 逆元线性递推 $a^{-1}\equiv(n-\frac{n}{a})(n\bmod a)^{-1}\pmod{n}$。

求 $\binom{100}{73}\bmod 101$。

\[\begin{aligned} &\binom{100}{73}\pmod{101}\\ &\equiv 100!\cdot(73!)^{-1}\cdot(27!)^{-1}\\ &\equiv 100!\cdot(-100!)^{-1}\\ &\equiv-1\\ &\equiv100 \end{aligned} \]

灵魂一步：$27!$ 逐项求逆后可以接在 $73!$ 后面。

求 $\binom{m}{p-1}\bmod p$。
$(-1)^{m}$。

求 $\binom{2023}{101}\bmod 101$。

\[\begin{aligned} &\frac{2023!}{101!\cdot1922!}\\ &\equiv\frac{2023\cdot2022\cdots\cdot 1923}{101!}\\ &\equiv\frac{2020}{101}\cdot\text{缩系}\\ &\equiv20 \end{aligned} \]

$\binom{n}{p}\equiv\lfloor\frac{n}{p}\rfloor\pmod{p}$。

群论

群的定义

定义群 $(G,\ast)$

群是封闭的，对于 $\forall f,g \in G$ 满足 $f \ast g \in G$
存在单位元 $e$ 满足 $c g \in G$ 有 $g \ast e = e \ast g$
$\forall g \in G$ 满足 $\exists g^{-1} \ast g = e$
群的运算具有结合律。
单位元 $e$ 有唯一性，proof：假若存在两个单元元 $e_1,e_2$ 则 $e_1 \ast e_2 = e_1 = e_2$ 与 $e_1 \not = e_2$ 矛盾，故单位元具有唯一性。
同理逆元同样具有唯一性。
群内的运算不一定满足结合律。
若群内的元素有限则为有限群，否则为无限群。
若群的运算不具有交换律则成为非交换群，否则为交换群。

举几个例子：

$(\mathbb{Z},+)$ 是一个无限群

$(\mathbb{Z_n^{ \times }},+)$ 是一个有限群

$M_{n}(R)$ 和 $S_{n}\{(1,2...n) \to (a_1,a_2...a_n)\}$ 是非交换群

置换群

\[f \ast g = f(g(1,2...n)) \]

子群

只包含单位元的子群被称为平凡子群。
如何找非平凡子群：取 $f \in G \not = e$ 对 $f$ 不断做二元运算和逆元运算，得到的结果和它本身加入群 $G'$ 则 $G'$ 构成 $G$ 的一个非平凡子群。
$(n\mathbb{Z},+)$ 是 $(\mathbb{Z},+)$ 的一个子群。

循环群

$G = \{a^m | m \in \mathbb{Z_n}\}$ 我们称群 $G$ 由 $a$ 生成，也认为 $a$ 是群 $G$ 的生成元，$o(G) = o(a)$，记作 $G = \left\langle a \right\rangle$

群同构

定义群 $(G_1,\ast_1)$ 与 $(G_2,\ast_2)$ 若存在映射 $f(x \in G_1) = y \in G_2$ 对于 $\forall g_1,g_2 \in G_2$ 满足 $f(g_1 \ast g_2) = f(g_1) \ast_2 f(g_2)$ 则称 $G_1$ 与 $G_2$ 同构。

对于任意 $a,n$ 满足 $\gcd(a,n) = 1$ 则 $\{\mathbb{Z_n},\times\} = \left\langle a \right\rangle$

满足 $g^{k} = e$ 的最小 $k$ 称为 $g$ 在群 $G$ 中的阶。记作 $o(k)$。

对于有限群 $G$ 有 $o(a^x) = \frac{o(a)}{\gcd(o(a),x)}$

拉格朗日定理

若 $H$ 是 $G$ 的一个子群，则 $|H| {\large\text{|}}|G|$

Proof：

定义群 $\{G,\ast \}$ 与它的一个子群 $H$。
下面证明对于 $\forall g_i,g_j \in G$ 要么 $g_i \ast H = g_j \ast H$ 要么 $g_i \ast H \cap g_j \ast H = \varnothing$

假若 $g_i \ast H \cap g_j \ast H \not = \varnothing$ 那么 $\exists h_k,h_w$ 使得 $g_i \ast h_k = g_j \ast h_w$，也就是说 $g_i \ast h_k \ast h_w^{-1} = g_j$ 又因为 $h_k \ast h_w^{-1} \in H$ 所以 $g_j \in g_i \ast H$ 所以 $g_j \ast H \in g_i \ast H$ 同理可得 $g_i \ast H \in g_j \ast H$ 所以 $g_i \ast H = g_j \ast H$

阶的性质

在有限交换群 $G$ 中若 $\gcd(o(a),o(b)) = 1$ 则有 $o(a \ast b) = o(a) \times o(b)$。
在一个有限交换群中 $G$ 中，$\max(o(g)) = \operatorname{lcm}(o(g))$

Proof：

令 $o(g_1) = \max(o(g))$ 若 $\exists g_2 \nmid o(g_1)$

$\exists p$ 满足 $V_p(g_2) > V_p(g_1)$

有 $o(g_2^{\frac{g_2}{V_p(g_2)}}) = V_p(g_2)$

有 $o(g_1^{V_p(g_1)}) = \frac{o(g_1)}{V_p(g_1)}$

因为 $\gcd(\frac{o(g_1)}{V_p(g_1)},V_p(g_2)) = 1$ 所以 $o(g_1^{V_p(g_1)} \ast g_2^{\frac{g_2}{V_p(g_2)}}) = \frac{o(g_1)}{V_p(g_1)} \times V_p(g_2) > o(g_1)$

与 $o(g_1) = \max(o(g))$ 矛盾，故 $\forall g_2 \mid o(g_1)$

原根

若 $g$ 是群 $(\mathbb{Z},\times)$ 的原根，有 $(g^{k})^{-1} = g^{n-1-k}$ 以及 $g^{m} \ast g^{n} = g^{m+n}$
群 $(\mathbb{Z_n},\times)$ 的原根个数是 $\varphi(n) - 1$，可以通过构造同构的加法群得到此结论。

置换群

Burnside 引理：$A,B$ 为有限集合，$X$ 为 $A \to B$ 的映射组成的集合，$G$ 是 $A$ 上的置换群，$X$ 中映射在 $G$ 的置换下封闭，$|\frac{X}{G}|$ 为 $X$ 中映射的等价类数量，$X^g = \{x|x \in X,g(x) = x\}$，有：