整除部分总结

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

整除部分脉络.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中,互素的本质就是无公共素数列$
一个小的建议，将所有数拆分为素数列乘积，可以很清楚的分析整除的情况

$类似的，若(a,r)=1，则(a,b)=(a,br),实质上r的乘积并未增加共同的素数列$
这时一个好的构造技巧，可用于区别奇偶数的公因数，毕竟奇数永远与2互素。

第三、四层知识

(4) $最小公倍数及多整数最大公因数最小公倍数求解$
(5) $贝祖等式及线性递推法，多元一次方程整数解法$

最后编辑于：2021.03.31 20:43:35

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,427评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,551评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,747评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,939评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,955评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,737评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,448评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,352评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,834评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,992评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,133评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,815评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,477评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,022评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,147评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,398评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,077评论 2赞 355