咕咕咕
# 整除
## 定义 1.1 - 整除
$a\mid b$ 指 $\exists n \in \mathbb{Z}$ 使得 $an=b$ 满足传递性： $a\mid b,b\mid c$ .
则 $a\mid c$ 可加减性： $n\mid a,n\mid b$ .
则 $n\mid a\pm b$ 可乘性： $a\mid b,c\mid d$ 则 $ac\mid bd$ .
例题：证明 $8\mid 3^{2n+1}+5$.
$3^{2n+1}+5= 3^{2n+1} -3+8 =3(9^k-1)+5 = 3(9-1)(......)+5$ 故成立.
# 因数定理
## 定义 2.1 - 最大公约数和最小公倍数
最大公约数 $\gcd(a,b)=\max\{x\mid a,x\mid b\}$
最小公倍数 $\operatorname{lcm}(a,b)=\min\{a\mid x,b\mid x\}$
#### 引理 1 - 带余除法
$\forall a,b$，$\exists$ 唯一 $k,r$ 使得 $a=kb+r$ ($0\le r<b$) .
证明：构造集合 $S=\{x \in \mathbb{N}： x=a-k b, k \in \mathbb{Z}\}$
可知该集合必有最小值，设其为 $r$， $0\le r=a-kb$ .
存在性：设 $r \ge b$，带入知 $a-(k+1)b\ge 0$，另 $r'=a-(k+1)b$ .
由于 $b>0$，$r'<r$ 于假设 $r$ 最小不符 故 $0\le r <b$.
唯一性：假设有两种表示 $$ \left\{\begin{array}{} a=r_{i}+k_{i} b \\ a=r_{j}+k_{j} b \end{array}\right. $$ 则 $r_i-r_j=b(k_i-k_j)$，由于 $r<b$，则合法解只有 $r_i=r_j$ 情况，故写法唯一。
求证：$\operatorname{lcm}(a,b)\mid$ 其余公倍数 .
证明：设 $\operatorname{lcm}$ 为 $d$，其余任意一个公倍数为 $c$.
假设 $d\nmid c$，则设 $c \bmod d=r$，$r=c-kd$，所以 $r$ 也是公倍数且小于 $\operatorname{lcm}$ 与假设不符.
求证：$\gcd(a,b)=\gcd(a-b,b)$ .
显然设任意公约数为 $d$，$d\mid a,d\mid b$ 所以 $d\mid (a-b)$，故不影响结果.
## 2.2 - 辗转相除法
$\gcd(a,b)=\gcd(b,a\bmod b)$ .
求证辗转相除法的正确性?
由上一条，显然取余等效于多次的减法，故显然也正确
## 2.3 - 裴蜀定理
($a,b,x,y$ 均为非 $0$ 整数， $a,b$ 为定值)，总存在 $x,y$ 使得 $ax+by=\gcd(a,b)$，且设 $k$ 为正整数，$d$ 为 $\gcd(a,b)$ 则 $ax+by=kd$，证明自行查阅此处不深入.
由此可证，$a,b$ 的任意公因数 $c$ 整除其最大公约数 $d$.
因为 $d=ax+by$ 其中 $c\mid a,c\mid b$ 故 $c\mid d$ 整除具有互质可消性，即 $a\mid bc$，$ab$ 互质则 $a\mid c$ (互质指最大公约数为 $1$).
证明：存在 $x,y$ 使得 $ax+by=1$.
所以 $c=axc+byc$.
故 $a\mid c$.
# 质数定理
## 定义 3.1 - 质数
设 $n$ 是质数当且仅当 $n$ 只有 $1$ 和 $n$ 作为因子. 以下用 $p$ 来表示质数.
反证可知无数个质数.
#### 引理 2 - $p$ 和任意其余整数要么互质要么整除
由质数定义可知
#### 引理 3 - 若 $p\mid ab$ 则 $p\mid a$ 或 $p\mid b$
由整除消去性可知.
## 3.2 - 算数基本定理(唯一分解定理)
任意正整数 $n=\prod_{i=1}^{k} p_i ^ {z_i}$ (除了1) 称为**标准分解式**.
文字描述就是说：一个大于一的正整数可以分解成若干质数的乘积，若忽视质因子顺序，则分解方式唯一.
证明：
可分解性： 数学归纳法， $2$ 自己是质数肯定成立，设 $2\sim k$ 成立，则若 $k+1$ 是质数自然满足，不是质数则可以分解出至少两个因数，两个因数可以分解，故可以分解.
唯一性： 设两种分解方案 $p,q$，设 $n$ 是最小的有多种方案的数.
两种方案都必有一个因子整除 $n$，由于是质数所以这个因子是相等的，把 $n$ 除以 这个因子得出一个更小的数，这个数依然有多种分解，与 $n$ 的最小性违背，所以分解唯一 $v_p(n)$ 表示 $n$ 的标准式中因子 $p$ 的指数.
性质：
$$v_{p}(n_1,n_2) = v_{p} (n_{1}) +v_{p} (n_{2}) $$$$v_p(gcd(n1,n2))= \min(v_p(n_1),v_p(n_2))$$$$v_p(lcm(n1,n2))= \max(v_p(n_1),v_p(n_2))$$$$ v_p(n_1+n_2) \left\{\begin{matrix} =\min(v_p(n1),v_p(n_2)) \ \ (v_p(n1) \neq v_p(n_2)) \\ \ge v_p(n_1) \ \ (v_p(n1) = v_p(n_2)) \end{matrix}\right. $$ $$v_p(n!)=\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor $$$$v_p(C_n^m)=\sum_{i=1 \to \infty} \left \lfloor \frac{n}{p^i} \right \rfloor -\left \lfloor \frac{m}{p^i} \right \rfloor-\left \lfloor \frac{n-m}{p^i} \right \rfloor$$ 这个式子的含义十分特别，它恰巧是 $n+(n-m)$ 在 $p$ 进制下的进位次数.
## 3.3 - 因数相关推论
设 $n=\prod_{i=1}^{k} p_i ^ {z_i}$
1. 设 $m=\prod_{i=1}^{k} p_i ^ {f_i}$，则 $m\mid n$ 等效于 $f_i\le z_i(1 \le i \le k)$
2. 因数个数公式 $$\tau(n) =\prod_{i=1}^k (z_i+1) $$
3. 因数和公式 $$\sigma(n) = \prod_{i=1}^k \frac{p_{i}^{z_{i+1}}-1}{p_i-1} $$
4. 因数积公式：$$n^{\frac{\tau(n)}{2}}$$
例题：
1. $p$ 为质数，$x、y$ 是正整数，解方程 $p^x=y^3+1$ $y^3+1=(y+1)(y^2-y+1)$
特判其中一个是一解得 $y=1,p=2,x=1$。
$\gcd(y+1,y^2-y+1)=\gcd(y+1,3)$ (辗转相除法) 故 $p=3$，解得 $x=3,y=3$。
## 定理 3.4 - 设 $n,m$ 唯一分解式为 $n=\prod_{i=1}^{k} p_i ^ {f_i} ,m=\prod_{i=1}^{k} p_i ^ {g_i}$ 则 $\gcd(n,m)= \prod_{i=1}^{k} p_i ^ {\min(f_i,g_i)},\operatorname{lcm}(n,m)= \prod_{i=1}^{k} p_i ^ {\max(f_i,g_i)}$.
#### 推论 4
以下用$(,)$表示 $\gcd$.
1. $(ma,mb)=m(a,b)$.
证明：略.
2. $(a,uv)=(a,(a,u)v)$.
证明：$(a,(a,u)v)=((a,av),uv)=(a,uv)$.
3. $(u,v)=1 \Rightarrow (a,uv) = (a,u)(a,v)$.
证明：参考分解，$u,v$ 无公因数所以分开计算不影响结果.
4. $(a,b)=(c,d)=1 \Rightarrow (ab,cd)=(a,c)(a,d)(b,c)(b,d)$，就是推广的 3.
5. $(a,b)=1 \Rightarrow (a^k ,b^k)=1$.
6. $gcd(a,b)\times lcm(a,b)=ab$.
证明：参考唯一分解，因此上述最大公约数的性质对最小公倍数成立.