整除部分总结

总体来看，整个章节的脉络可以这么看

整除部分脉络.png

为了节省时间，也为了简洁性，就在这里大概的讲一讲。
(前置条件从略)

第一层知识

(1) $(欧式除法): \forall a,b,r \in N^+,(a,b \neq 1), \quad , \exists q \in N, 有唯一的a=q*b+r, \ r \in [0,b)$
$若r=0,则称b整除a,记作b|a$
$其中q称作不完全商,r称作余数$

以下给出整除的几个简单性质，传递性，线性稳定性以及相等

$若c|b, b|a,则c|a \ [传递性]$
$若c|a, c|b,则\forall s,t \in Z,\ c|(sa+tb) \quad [线性稳定性]$
$若a|b, b|a,则 \ a= \pm b [这里采用国内的素数域拓展到负数，潘承洞书中拓展了，不影响整体]$
$以上证明从略，2可以通过证明c|ka 和c|a+b推出$

第二层知识&部分第三、四层知识

(2) $素数，素因子[包含筛法和算数基本定理以及有关阶乘的整除判定]$

$素数(采用正素数定义):因子只有自身和1$
$素因子: 整数的素数因子$
$素数基本定理: 所有整数都可以写做素数和1的乘积，简单证明，合数会分解为素数或是更小的合数,$
$不断分解，直至分解为素数乘积。$

几个关于素数的简单知识点

$整数都可以表示为qb+r的形式，类似一个余数系$
$若n为一个正合数,p为n的非1最小因数,则p为素数,且p \leq \sqrt{n}$
关于这点的证明: $p*p \leq n=p* \frac{n}{p} , 且若p不为素数，则p可分为素数与1的乘积$
这一定理确定了排除合数的方法，即排除能被小于 $\sqrt{n}$ 的非1因子整除的数
$若一个数n不能被所有小于\sqrt{n}的非1正因子整除，则n为素数$
$由上式可推出平凡筛法，即去除\sqrt{N} 范围内所有素数的倍数，即可得出规模为N的素数表$
$素数的个数为无穷个，证明很多，其中欧几里得的证明非常巧妙，可以假设素数有限，$
$并假设素数列为p_1p_2...p_n,设N=\prod_{i=1}^{n}{p_i},利用N+1来证明矛盾$
$利用数都可以用qb+r来表示，可以证明大于5的素数都分布在6N\pm1上，类似的也可以推出其它的表达$

素数基本定理的数学表达

$\forall n>1(n \in Z), \exists p_i \in Primes: \ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_s^{\alpha_s}$

(3) $最大公因数\&最小公倍数$
$\forall a,b\in Z的最大公因数记作gcd(a,b)或是(a,b)$
$\forall a,b\in Z的最小公倍数记作[a,b]$

(重点)互素:

$\forall a,b\in N^+, 若 \ gcd(a,b)=1,a,b互素$

从这里会开始建立一个有关整除和公因数的体系，请注意

$T1:已知a=qb+r,(a,b)=(b,r)$
$证明 : let \ d|a, d|b,a=qb+r$
$\qquad then \qquad d|a+(-q)*b$
$\qquad \therefore d|r$
$\qquad let \ d=gcd(a,b)\ , d'=gcd(b,r)$
$\qquad d'\leq d$
$\qquad \therefore d=gcd(b,r)$
$\qquad \therefore (a,b)=(b,r)$
前置:最大公因数大于等于所有因数，这是最基本的，也是常用的
$T2:当T1不断进行时,r是单减的，有限步内r=0,(b,r)=(r,0),则此时最小的非0的r就是最大公因数$
这个就是辗转相除法的基本方法
$T3:很显然的gcd(a,b)|(sa+tb),进一步的\exists s,t\in Z使得gcd(a,b)=sa+tb$
$这是显然的,记gcd(a,b)为d,将a,b分别写做k_1*d,k_2*d$
$这就是解一个s*k_1+t*k_2=1的不定方程，恒有整数解,这个会在后面讨论证法$
$这个式子被称作贝祖等式，提示,可以先把k_1,k_2转化为互素的形式$

前面是如何求最大公因数，以及最大公因数与原数的关系，以下则转向对公因数与整除的关系

$T4: 最大公因数的充要条件与性质$
$(1) d|a \ , d|b$
$(2) \forall \ d'|a \ d'|b,有d'|d$
证明可以通过素数分解来得到,最大公因数d其实就是共有素数的全部的幂次乘积，而公因数d'则是共有素数的幂次乘积

$T5:互素整数的构造$
$( \frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$
可用素数因数分解来证明
$T6:(m*b,m*b)=m*(a,b)$
也可用素数因数分解来证明，左右两端同乘m即可
$T7: 一个小例子c \neq 0 ,若c|ab \ ,(a,c)=1 ,则c|b$
$这实际上就是c的素数列必须包含于b中,互素的本质就是无公共素数列$
一个小的建议，将所有数拆分为素数列乘积，可以很清楚的分析整除的情况