数论与组合数学

数论部分

数论简介、素数、算术基本 定理

自然数的基本性质

  • 数学归纳法PMI (Principle of Mathematical Induction)

​ 如果 $p_1 $ 是真的，并且$ p_n \Rightarrow p_{n+1} $，那么 $ p_n$对于所有自然数来说都是真的。

  • 良序定理WOP (Well Ordering Principle)

​ 每个非空集合都存在一个最小元素。

GCD(Greatest Common Divisor)

  • 整除：a|b 读作a整除b。b=a*整数

  • 辗转相除法

1
2
3
4
5
int gcd(int m,int n)
{
    if(n==0) return m;
    else return gcd(n,m%n);
}
  • 定理：
    $$
    { Let } g=\operatorname{gcd}(a, b) \text {, then } \exists v_{0}, y_{0} \in Z \text { such that } g=a x_{0}+b y_{0} \text {. }
    $$

例题

img

同余、中国剩余定理

同余

  • 定义：$a \equiv b \text { mod } m \text { 代表 } m \mid(a-b)(a, b, m \in Z, m \neq 0)$

  • 性质（3）

欧拉定理

  • 欧拉梯度函数：$\phi(m)$表示1…m中与m互质元素的个数。（既约剩余系）

  • 完全剩余系：mod m的互不同余的所有数的集合
    既约剩余系：mod m的互不同余且和m互质的所有数的集合

  • 欧拉定理：$\mathrm{ If } \text { gcd(a,m)=1 }, \text a^{\phi(m)}\equiv1 \text { mod m}.$​

  • 费马小定理：如果p为质数，那么$a^p\equiv a(mod \ p)$

  • Wilson’s Theorem: $\text { If }p\text{ is a prime, then }(p-1)!\equiv-1 \ mod \ p$

例题：求一个幂的最后一位

img

模逆元

img

例题：欧几里得拓展算法求模逆元

img

线性同余方程组

线性同余方程组: $\text {ax=b mod m}$
有解判定：令g=gcd(a,m)，当且仅当g|b时，ax=b mod m才有解，且有g mod m个解。

例题：求解线性同余方程

img

中国剩余定理

img

Hensel 引理

img

两道例题

img

img

模多项式

$\begin{aligned}&f(x)\equiv0\mathrm{ mod }p\text{ (p is a prime) of degree }n\text{ has at most }n \text{ solutions.}\end{aligned}$​

img

阶

  • 定义：gcd(a,m)=1,满足$a^h=1mod$ $m$的最小正整数h是a mod m 的阶，写作$h=ord_m\left(a\right)$

  • 定理：

    • 其余满足该式的幂次都是h的倍数

    • $a^k$ mod $m$的阶是$\frac h{qcd(k,h)}$

    • $a \ mod\ m$的阶是h，$b \mod \ m$的阶是k，hk互素，则ab mod m的阶是hk

原根

  • 定义：a mod m的阶是$\phi(m)$,则a是原根

  • 定理：

    • p, q是素数，$q^e|p-1$,则存在元素mod p的阶是$q^e$

  • 原根数量：mod m的原根数量是$\phi(\phi(m))$

  • 原根存在判定：当且仅当$m=1,2,4,p^e,2p^e$​时，m存在原根

平方剩余、二次互反律

平方剩余

  • 定义: $\text{p是素数,}a\neq0\mathrm{ }mod\mathrm{ }p\text{,当}a=b^2 \ mod\mathrm{ }p\text{时,a是平方剩余,否则是平方非剩余}$​
  • 定理：$a\neq0\mathrm{ }mod\mathrm{ }p,a^{\frac{p-1}2}=1\mathrm{ }mod\mathrm{ }p\Rightarrow\text{а是平方剩余}$​

15是17的平方剩余：$15^{\frac{17-1}2}\equiv1\mathrm{ mod }17.$​

12不是17的平方剩余：$12^{\frac{17-1}2}\equiv-1 mod 17.$​

例题：形式转换

img

Legendre符号

  • 定义：

p为素数
$$
\left( \frac{a}{p} \right) = \begin{cases}
1 & \text{如果 } a \text{ 是模 } p \text{ 的平方剩余} \
-1 & \text{如果 } a \text{ 不是模 } p \text{ 的平方剩余}
\end{cases}
$$

$$
\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} \mod p
$$

最后得到结果无非就是 $1$ 或 $-1$，可见 Table of x^k mod m。

  • 意义：

由Legendre符号的定义可以看出，如果能够很快地算出它的值，那么就会立刻知道同余式是否有解。具体地说：

$$
x^2 \equiv a \pmod{p}, \quad p \text{ 是奇素数}, \quad a \in \mathbb{Z}
$$

  1. 当 $\left(\frac{a}{p}\right) = 1$ 时，$a$ 是模 $p$ 的平方剩余，根据平方剩余的定义，同余式有解。

  2. 当 $\left(\frac{a}{p}\right) = 0$ 时，有 $p \mid a \Rightarrow a \equiv 0 \pmod{p}$，此时同余式 $x^2 \equiv a \equiv 0 \pmod{p}$ 有唯一解 $x \equiv 0 \pmod{p}$。

  3. 当 $\left(\frac{a}{p}\right) = -1$ 时，$a$ 是模 $p$ 的平方非剩余，由平方非剩余的定义，同余式无解。

定理及例题 ：

img

高斯引理

img

  • 小结论：$\left(\frac2p\right)=(-1)^{\frac{p^2-1}8}$

二次互反律

  • 定义：当p、q都为素数时

$
\left( \frac{p}{q} \right) = \begin{cases}
+\left( \frac{q}{p} \right) & \text{如果 } p \equiv 1 \pmod{4} \text{ 或 } q \equiv 1 \pmod{4} \
-\left( \frac{q}{p} \right) & \text{如果 } p \equiv q \equiv 3 \pmod{4}
\end{cases}
$

大量的练习题：

【Toneli-Shanks算法可用于求解二次同余方程组的解】

分圆多项式、算术函数

欧拉函数的计算

img

分圆多项式

  • 定义：$\text{对正整数n来说,能整除}x^n-1\text{但不能整除}x^k-1(k<n)\text{的多项式是分圆多项式,用}\phi_n\left(x\right)\text{表示。}$​

img

  • 定理1：$$ x^n-1=\prod_{d|n} \phi_d\left(x\right)$$
  • 定理2：$$ \phi_n\left(x\right)\text{的最高次}n=\phi(x)$$

算数函数

  • 加性 f(mn)=f(m)+f(n)
  • 乘性 f(mn)=f(m)f(n)

函数举例：

img

连分式

  • Golden Ratio：[1,1,1,1,1...]

  • sqrt(2)：[1,2,2,2,2...]

有理数（分数）转化：

img

无理数转化：

Real number $x$, compute integers $a_0,a_1,\cdots$,such that $a_0=\lfloor x\rfloor .$
$$x=a_0+\frac1{a_1+\frac1{a_2+\frac1{\ddots+\frac1{a_n}}}}$$
$x_1=\frac{1}{x-a_0}$,then $a_1=\lfloor x_1\rfloor$,

$x_2=\frac1{x_1-a_1}$, then $a_2=\lfloor x_2\rfloor,\cdots$​

组合数学部分

基本计数原理

加法原理

乘法原理

例题：

img

数学归纳法

PMI

鸽巢原理

img

容斥原理

img

错排问题

有n个信封，n封信。求每封信都对应错误信封的方案数量

  • 递推公式：

    • D(1)=0,D(2)=1

    • D(n)=(n-1)(D(n-1)+D(n-2))

  • 生成函数：$d_n =n!\sum_{k=0}^n\frac{(-1)^k}{k!}$

排列与组合

基础

img

二项式系数

  • 二项式系数：$$(x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k.$$​
  • 证明：

img

划分

组成

针对n个相同的球，放到k个同种箱子（是否可空）

img

  • 正整数n有$2^{n-1}$个不同划分

集合划分

针对n个不相同的球，放到k个不同种箱子

  • 第二种斯特林数：The number of partitions of an 𝑛-element set into exactly 𝑘 nonempty parts is the Stirling number of the second kind 𝑆(𝑛, 𝑘) .

$$
\text{For all positive integers }k<n,\
S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k).
$$

S(7,4)与S(8,3)谁更大？

img

  • $\text{Bell number }B_n$

$$
B_n=\sum_{k=0}^nS\left(n,k\right)
$$

​ e.g. $ 𝐵_3$ = 5. $𝐵_1$ = 1. We define $𝐵_0$

整数划分

n个相同的球，放到k个相同箱子的不同分法

  • 费勒斯图

结论1：将n个分为k堆的方案数=将n个元素最多的一堆中有k个元素的方案数

结论2：集合划分为奇数份的方案数等于所有总数为n的自共轭图的种数。

生成函数

  • 两项递推类型

例题：求递推公式

img

img

  • 三项类型

img

斐波那契

  • 结论及证明：

img

卡特兰数

应用

  • 括号匹配
  • 不过对角线方案数量

img

通项公式

$$
C_n=\frac1{n+1}\binom{2n}n
$$