整数的可除性

整除

Eratoshenes筛法

定理：设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数且 $p\leq\sqrt{n}$
Eratoshene筛法：设n是正整数，如果对所有素数 $p\leq\sqrt{n}$ 都有p $\nmid$ n，则n一定是素数。

证明：显而易见，如果第一个定理是成立的，那么就很容易得到Eratoshenes筛法，所以这里只需要证明第一个定理
反证法，假设n的大于1的最小正因数p是合数，那么显然 $\exists$ q>1， q | p，则有q | n，所以q也是n的一个大于1的正因数，且q<p，这与p是n的大于1的最小正因数的前提相违，故p是素数。
对于第二个部分同样使用反证法，假设n的大于1的最小正因数 $p>\sqrt{n}$ ，因为p是n的因数，所以可以设n=pq
$\because$ p是n的最小正因数
$\therefore q>p>\sqrt{n}$
则 $pq>\sqrt{n}*\sqrt{n}=n$ ，这与前提条件相违背
故 $p\leq\sqrt{n}$

欧几里得除法

设a，b是两个整数，其中b>0，则存在唯一的整数q，r，使得a=qb+r且 $0\leq r <b$

证明：存在性
可以将数轴分成无数个长度为b的区间，即 $\cdots,-2b,-b,0,b,2b,\cdots$
则整数a必然落在其中的一个区间上
$\therefore\exists q$ 使得 $qb\leq a < (q+1)b$
令 $r=a-qb$ ，则 $a=qb+r$
唯一性
假设分别有整数 $q,r,q_1,r_1$ 使得：
$a=qb+r$ $(0\leq r<b)$
$a=q_1b+r_1$ $(0\leq r_1<b)$
则 $(q-q_1)b=-(r-r_1)$
如果 $q\neq q_1$ 则 $|(q-q_1)b|\geq b$ ，而 $|-(r-r_1)|<b$ ，显然矛盾
故 $q=q_1$ $r=r_1$

定理：设a,b,c是三个全不为零的整数，如果存在整数q使得a=qb+c，则(a,b)=(b,c)

证明：设d=(a,b)，则d | a，d | b，由整除的运算定理可知：
d | (a-qb)，d | c
$\therefore$ d是b，c的一个公因数
设d'=(b,c)，则d $\leq$ d'且d' | b，d' | c
则d' | (qb+c)，d' | a
$\therefore$ d'是a,b的一个公因数，则d' $\leq$ d
$\therefore$ d=d'
即(a,b)=(b,c)

广义欧几里得除法：设a,b是两个任意的正整数，记 $r_{-2}=a, r_{-1}=b$ ，则反复运用欧几里得除法有：
$r_{-2}=q_0r_{-1}+r_0$
$r_{-1}=q_1r_0+r_1$
$\dots$
$r_{n-1}=q_{n+1}r_n+r_{n+1}$
$r_n=q_{n+2}r_{n+1}+0$
则 $r_{n+1}$ 是a,b的最大公因数
通过上面的定理就很容易得到广义欧几里得除法的证明
贝祖等式：设a,b是任意的两个正整数，则存在整数s,t使得sa+tb=(a,b)

贝祖等式的证明同样可以由广义欧几里得除法得到，因为广义欧几里得除法得出了一系列的等式，而 $r_{n+1}$ 就等于(a,b)，那么在上面的等式用 $r_{n+1}$ 依次向上取代便可得到贝祖等式

定理：整数a,b互素的充分必要条件是存在整数s,t使得sa+tb=1

证明：必要性，不难证明，(a,b)=1 $\rightarrow$ sa+tb=1
充分性
设d | a, d | b
$\because$ sa+tb=1
$\therefore$ d | (sa+tb) = 1
$\therefore$ d = 1
也就是说只有1能够同时整除a,b，即(a,b)=1

算术基本定理

任意整数n>1都可以表示成素数的乘积，且不考虑乘积顺序的情况下，该表达式是唯一的，即 $n=p_1\cdots p_s$ ，其中 $p_1\leq\cdots\leq p_s$
标准分解式：任意整数n>1可以唯一的表示成： $n=p_1^{a_1}\cdots p_s^{a_s}$ ，其中 $a_i$ >0， $p_i<p_j(i<j)$ 是素数。

定理：设a,b是两个正整数，且都有素数因数分解式
$a=p_1^{a_1}\cdots p_s^{a_s}$
$b=p_1^{b_1}\cdots p_s^{b_s}$
则a,b的最大公因数和最小公倍数为：
$(a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}$ ，其中 $\varphi_i=min(a_i,b_i),i=1,\dots,s$
$[a,b]=p_1^{\psi_1}\cdots p_s^{\psi_s}$ ，其中 $\psi_i=max(a_i,b_i),i=1,\dots,s$

推论1：(a,b)[a,b]=a,b

证明.
$\because(a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}$
$[a,b]=p_1^{\psi_1}\cdots p_s^{\psi_s}$
$\therefore (a,b)[a,b]=p_1^{\varphi_1+\psi_1}\cdots p_s^{\varphi_s+\psi_s}$
而 $\varphi_i=min(a_i,b_i)$ ， $\psi_i=max(a_i,b_i)$
$\because max(a,b)+min(a,b)=a+b$
$\therefore \varphi_i+\psi_i=a_i+b_i$
$\therefore (a,b)[a,b]=p_1^{a_i+b_i}\cdots p_s^{a_s+b_s}=ab$

推论2： $\frac{a}{(a,b)}$ 与 $\frac{b}{(a,b)}$ 互素

证明.
$\because (a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}(\varphi_i=mid(\alpha_i,\beta_i))$
$\therefore \frac{a}{(a,b)}=p_1^{\alpha_1-mid(\alpha_1,\beta_1)}\cdots p_s^{\alpha_s-mid(\alpha_s,\beta_s)}$
$\frac{b}{(a,b)}=p_1^{\beta_1-mid(\alpha_1,\beta_1)}\cdots p_s^{\beta_s-mid(\alpha_s,\beta_s)}$
$\because mid(a-mid(a,b),b-mid(a,b))=0$
$\therefore (\frac{a}{(a,b)},\frac{b}{(a,b)})=p_1^0\cdots p_s^0=1$
即 $\frac{a}{(a,b)}$ 与 $\frac{b}{(a,b)}$ 互素

最后编辑于：2019.10.22 23:28:39

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

整数的可除性

整除

Eratoshenes筛法

欧几里得除法

算术基本定理

推荐阅读更多精彩内容