整除（easy）
整除定义
若 \(\forall a,b\in Z,b\ne 0,\exists q\in Z.\ s.t.\ a=qb.\) 则称：
\(b\) 整除 \(a\) ，或 \(a\) 被 \(b\) 整除，记为：\(b\mid a\)
\(b\) 不整除 \(a\) ：\(b\nmid a\)
整除性质
设 \(a,b,c\in Z\)
- 若 \(b\mid a\) , \(a\mid b\) , 则 \(b=\pm a\).
- 若 \(a\mid b\) , \(b\mid c\) , 则 \(a\mid c\).
- 若 \(c\mid a\) , \(c\mid b\) , 则 \(c\mid ua+vb\), \(\ u,v\in Z\).
- 若 \(c\mid a_{1}\) , \(...\) , \(c\mid a_{k}\) , 则 \(\forall u_{1},\) \(...\) \(, u_{k} \in Z,\ s.t.\ c\mid (u_{1}a_{1}+\) \(...\) \(+u_{k}a_{k})\)
带余除法
定义
\(\forall a,b\in Z,b\ne 0,a=qb+r，0\le r<|b|.\)
\(q\)：不完全商， \(r\)：余数
显然当 \(r=0\) 时 \(b\mid a\)
存在性证明
-
当 \(b\mid a\) 时，取 \(q= \frac{a}{b},r=0\)
-
当 \(b\nmid a\) 时，取集合 \(T=\{a-kb,\ k=0,\pm 1,\pm 2 ...\}\)
设 \({T}'\) 为 \(T\) 的正整数子集，则存在其中最小正整数 \(t_{0}=a-k,\ a-k_{0}b>0\)
下证 \(t_{0}<|b|\)：
若 \(t_{0}=|b|\) 则 \(b\mid a\)，矛盾
若 \(t_{0}>|b|\) 则 \(\exists t_{1}=t_{0}-|b|\in T\) 且 \(0<t_{1}<t_{0}\) 与 \(t_{0}\) 最小矛盾
所以 \(0<t_{0}<|b|,\ a=k_{0}b+t_{0},\ q=k_{0},\ r=t_{0}\)
唯一性证明
如果 \(a=q_{1}b+r_{1},a=q_{2}b+r_{2},0\le r_{1},r_{2}<b\ (q_{1} \ne q_{2},\ r_{1}\ne r_{2})\)
则 \(b\le |(q_{1}-q_{2})b|=|-(r_{1}-r_{2})|<b\) 矛盾
前：因为 \(q_{1} \ne q_{2}\) ；后： 因为 \(0\le r_{1},r_{2}<b\)
所以 \(q_{1}= q_{2},\ r_{1}= r_{2}\) 即 \(q,r\) 唯一
最大公因数 \(gcd\) 与最小公倍数 \(lcm\)
公因子
\(a,b\in Z\) ，若整数 \(c\mid a\) , \(c\mid b\) ,则 \(c\) 称为 \(a,b\) 的公因子
最大公因子
定义（三个条件）
- \(c>0\)
- \(c\) 是 \(a,b\) 的公因子
- \(a,b\) 的任何公因子都整除 \(c\)
则 \(c\) 称为 \(a,b\) 的最大公因子（ \(c\) 唯一）
记为：\(c=(a,b)\) 或 \(c=gcd(a,b)\)
性质
- \((a,b)=(\pm a,\pm b)=(|a|,|b|)\)
- \((0,a)=|a|\)
- 若 \(a\mid b\) ，则 \((a,b)=a\)
- \(\forall x,y\in Z,(a,b)\mid (ax+by)\)
- 若 \(a=bq+c,q\in Z\) ，则 \((a,b)=(b,c)\)
- 若 \((a,c)=1,b\mid c\) ，则 \((a,b)=1\)
- \((\frac{a}{(a,b)},\frac{b}{(a,b)})=1\)
- 设 \(a_{1},...,a_{k}\) 是 \(k\) 个不全为零的整数
\((a_{1},a_{2},...,a_{k})=(a_{1},(a_{2},...,a_{k}))=...=(a_{1},(a_{2},...,(a_{k-1},a_{k})...))\)
公倍数与最小公倍数 (easy)
\(m>0,a\mid m,b\mid m,m\mid k\)（\(k\) 为任何公倍数)
性质类比最小公因数
则 \(m=[a,b]=lcm(a,b)\)
性质
辗转相除法 (medium)(*point)
欧几里得除法/辗转相除法
过程
\[\begin{align*} &设\ a,b\in Z,\ 记\ r_{0}=a,r_{1}=b,\ 有：\\&r_{0}=q_{1}r_{1}+r_{2} & 0<r_{2}<r_{1}\\&r_{1}=q_{2}r_{2}+r_{3} & 0<r_{3}<r_{2}\\&\vdots &\vdots \\&r_{l-2}=q_{l-1}r_{l-1}+r_{l} & 0<r_{l}<r_{l-1}\\&r_{l-1}=q_{l}r_{l}\\&r_{l} = (a,b)\end{align*} \]网页奔溃了后面的没保存上，QAQ
一两百行的公式，有空再填坑
标签：知识点,...,公倍数,mid,因子,整除,同余,pm From： https://www.cnblogs.com/IrisHyaline/p/17160520.html