（参考）《数论算法》教案1章(整数的可除性)

1、第 1 章 整数的可除性内容1. 整除性2. 公因数、最大公因数3. 辗转相除法（欧几里得除法）4. 算术基本定理要点培养对数论问题的认识及证明问题的思路数论从研究整数开始，叫“整数论”。经进一步发展，叫做“数论”。确切地说，数论是研究整数性质的学科。自然数（正整数）负整数0（统称整数）。算术运算：加、减、乘、除（四则运算）。加法、减法和乘法在整数范围内可以毫无阻碍地进行。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。数论算法主要从应用角度出发，研究数论问题中实用的方法和技术。1.1 整除的概念 欧几里得除法(一) 整除概念【定义1.1.1】 设a, bZ（整数集合），b0，如果存在q

2、Z，使得abq，则称b整除a或a可被b整除，记作ba，且称a是b的倍数，b是a的因数（也可称为除数、约数、因子）。否则，称b不能整除a或a不能被b整除，记作ba。说明：（1） q也是a的因数，并将q写为a/b或；（2） 当b遍历整数a的所有因数时，b也遍历整数a的所有因数；（3） 当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数。例：设 a6，则有（1） 当b3时，q26/3（2） 当b1, 2, 3, 6,1,2,3,6时有b1,2,3,6, 1, 2, 3, 6（3） 当b1, 2, 3, 6, 1,2,3,6时有a/b6, 3, 2, 1, 6,3,2,1【特例】：（1） 0是任

3、何非零整数的倍数；（2） ±1是任何整数的因数；（3） 任何非零整数a是其自身的倍数，也是其自身的因数。(二) 性质（1） 设，则 。（证） abq aq(b) 其余类推。【例1.1.1】30的所有因数：±1，±2，±3，±5，±6，±15，±30（2） 传递性：，（证）且 bc，ab ac ca。（3） ，则（4） ，则对任意整数s、t，有推广：（5） 若，则a±b（证） ab ba a 1 ±1（6） （c0）（7） 若，则 (三) 例【例1.1.2】证明：若且，则。（证） 已知 。 。即m

4、7q所以 n3(7q)21q 。【例1.1.3】设。若，则。（证） 又 (ann)ann，即（由a2t1知2ta1，从而2tnann）【例1.1.4】设a, b是两个给定的非零整数，且有整数x, y，使得。证明：若且，则（证） 由且 。 n(axby)，即。注意到，由此也证明了例1.1.2。【例1.1.5】设是整系数多项式。若，则（证）由及 （k1, 2, , n） 。应用：若，那么。例：设，判断7能否整除。因 7q4，故只需判断：3082？答：不能(四) 素数（1） 定义（素数与合数）设整数p0, ±1。如果它除了显然约数±1, ±p外没有其它的约数，那么，就称

5、为素数（或质数、不可约数）。若a0, ±1，且不是素数，则称为合数。约定：素数一般指正整数。（2） 性质（a） 最小正因数必是素数（b） n是正整数，当2p且pn，则n是素数。（c） 素数有无穷多。（证）（c）：用反证法。假设只有有限个素数：。构造则 且a（i1, 2, , k）。 a必是合数 存在素数p，使得 。由假设知p等于某个一定整除但素数，矛盾。因此，假设是错误的，即素数必有无穷多个。性质（b）的应用：快速判断素数。扩展：设是全体素数按大小顺序排成的序列，以及。直接计算可得：， ， ， ， ， ， ， ，前五个是素数，后五个是合数，但都有一个比更大的素因数。未解决的问题：至今

6、还不知道是否有无穷多个k使是素数，也不知道是否有无穷多个k使是合数。(五) 欧几里德除法也叫带余数除法、除法算法初等数论的证明中最重要、最基本、最常用的工具之一。（1） 欧几里德除法：设a, b是两个给定的整数，b0。那么，一定存在唯一的一对整数q与r，满足, 约定：b>0。上式可表为, （2）（2） 存在性当时，可取，r0。当ba时，考虑集合，3b，2b，b，0，b，2b，3b，将实数分为长度为b的区间，a必落在某区间内，即存在整数q，使得qba(q1)b令rabq，则有, （3） 唯一性设有也满足（2）式，即 必有 当q时有 b，矛盾，故必有，。（4） 推论：的充要条件是r0。当aq

7、br时, 有。当满足时，就有 r0。（5） 一般形式设a, b是两个给定的整数，则对任意整数c，一定存在唯一的一对整数q与r，满足, （3）此外，的充要条件是。例：a100，b30，c10，则10r40，即1003*3010若c35，则35r65，即1002*3040若c50，则50r20，即1005*30(50)(六) 不完全商和余数【定义1.1.2】设abqr（），称q为a被b除所得的不完全商，称r为a被b除所得的余数。【推论】 ba的充要条件是a被b除所得的余数r0。余数的分类：1 最小非负余数 c0，0rb2 最小正余数 c1，1rb3 最大非正余数 cb1，b1r04 最大负余数 c

8、b，br05 最小绝对余数 b/2rb/2或b/2rb/2(七) 下整数与上整数【定义1.1.3】 设x是一个实数，称为下整数函数，其值为不大于x的最大整数。即x满足x1（原定义为：设x是一个实数，称x的整数部分为小于或等于x的最大整数，记为）上整数函数：表示不小于x的最小整数。即1xx四舍五入函数：函数是将x四舍五入的结果。说明 当aqbr（0r<b）时，有q，rab例：3，44，33，3，3.54，3.53，3.94，3.941.2 整数的表示(一) 整数的表示方法【定理1.2.1】 设p是大于1的正整数，则每个正整数n可以唯一地表示成其中为整数，0p（i0, 1, , k）且首项系

9、数0（即n）。【定义1.2.1】 用表示展开式其中0p1（i0,1,k），0，并称其为整数n的p进制表示。【推论1】 每个正整数都可以表示成不同的2的幂的和。因为对于二进制而言，系数只能为0或1。(二) 数制的转换（整数）十进制转换为p进制：除p取余p进制转换为十进制：用展开式计算1.3 最大公因数与欧几里得除法(一) 最大公因数【定义1.3.1】设是n个整数（n2）。若整数d是它们中每一个数的因数，那么d就称做的公因数（或公约数、公因子）。若整数不全为零，那么的公因数中最大的一个叫做最大公因数，记作。互素（互质）：当1时，称互素或互质。等价定义：d0是的最大公因数的数学表达式可表示为（1）；

10、（2）若，则ed。【例1.3.1】 求最大公因数（12, 18），（6, 10, -15），（n, n1）。（解）（用定义求）a112，a218，故其公因数是±1，±2，±3，±6，最大公因数是6。a16，a210，a315，它们的公约数是±1，且最大公因数(6, 10,15)1。小结论：任何n和n1的公约数都是±1。(二) 性质（1） （a） （2） （a，b）（b，a）一般情形其中是1，2，n的一个全排列。（3） 设a，b为正整数，若ba，则（a，b）b一般：为整数且0，（i2，3，n），则（）【例1.3.2】求(6, 12, 4

11、2)，(21, 56, 7)（解）因为612，642，所以(6, 12, 42)(6, 12)(6, 12)6又知721，756，故 (21, 56, 7)7（4） 设p为素数，a为整数，若pa，则p与a互素。（证）设d（p，a），则da，dp但p为素数，故d1或p。若dp，则由da知pa，与假设矛盾故d1，即(p, a)1（5） 设是n个不全为零的整数，则（i）与的公因数相同。（ii）()（证）由d知d，反之，若d，则必有d，故（i）成立。由（i）立得（ii）。（6） 设a、b为正整数，则（证）是性质（5）中（ii）的特例。一般情形：a、b为整数，则或均为整数，则（7） 设整数b0，则（0，

12、b）b一般形式：b0，则（0，b）（8） 设a，b，c是三个不全为零的整数，abqc，其中q是整数，则（a，b）（b，c）（证）设d（a，b），e（b，c）。则由da，db知dabqc知d为c的因数，从而de。同理可知ed，故de。意义：是快速求最大公因数d(a, b)的算法的理论基础。应用：设a，b0且ab，abqc，则 (a，b)(abq，b)(c，b)(b，c)【例1.3.3】计算（389, 189）和（8877，9988）（解）由性质8知（389，189）（389，189）（389189×2，189）（11，189）（189，11）（18911×17，11）（11，

13、2）1（注：本例大数在前，一般可不考虑两个数的顺序）（8877，9988）（8877，99888877×1）（8877，1111）（88771111×7，1111）（1100，1111）（1111，11）（0，11）11（9） 对任意的整数x，y，有推广： 应用：化简计算过程【例1.3.4】计算(51，809，17)。（解）(51，809，17)(17×3，809，17)(809，17)一般情形： （1i，jn）（10） 对任意整数x，有 注：性质（8）的一般情形。（证）设d(a，b)，e(a, bax)，f(aby, b) da，dbdbaxde，即de。ea，

14、ebaxe（bax）axbed，即ed，故de。应用：从右向左化简。【例1.3.5】 (389，750)(389，361)又如 (389，750)(389，27)(389，27)(119，27)(16，27)1（11） 设a，b均为偶数，则 (a，b)2(a/2，b/2)设a为偶数，b为奇数，则（a，b）（a/2，b）设a，b均为奇数，则（a，b）。应用：化简计算过程【例1.3.6】计算（108，240），（108，249）和（357，123）。（解）（108，240）2(54，120)2×2(27，60)（108，249）(54，249)(27，249）（357，123）(117，

15、123)(117，6)(117，3)3（12） 设p是素数，则一般情形【例1.3.7】（7, 56, 259）7，（7, 56, 259, 100）1（13） (a, b, c)（(a, b), c）一般情形 【例1.3.8】（48，90，91，14）（48，90），（91，14）（6，7）1或 (48，90，91，14)(48，90)，91，14)(2，91，14)(2，91)，14)(1，14)1应用：求多个整数最大公因子的一种方法。(三) 广义欧几里得除法（展转相除法） （1） 理论分析设整数ab0，记， ， ， （1）， ， 因 b>0故 必存在n，使得 （2） 结论【定理1.3

16、.1】设整数ab0，则（a，b），其中是欧几里得除法（1）中最后一个非零余数。（证）由性质8，（a，b）（，）（，）（，）再由性质7，（a，b） （3） 例【例1.3.9】利用展转相除法求（46480，39423）。（1）取最小非负余数（直观的方法）464801·39423 7057394325·7057 41387057 1·4138 29194138 1·2919 12192919 2·1219 4811219 2·481 257481 1·257 224257 1·224 33224 6·33 26

17、33 1·26 726 3·7 57 1·5 25 2·2 12 2·1所以 （46480，39423）1（2）取最小绝对余数（运算量较少的方法）464801·39423 7057394326·7057 29197075 2·2919 12192919 2·1219 4811219 3·481 224481 2·224 33224 7·33 733 5·7 27 3·2 12 2·1(四) 求（a，b）的欧几里得算法（1） 理论依据：性质8（2）

18、 思路：a) 利用性质6，将求两个整数的最大公因数转化为求两个非负整数的最大公因数。b) 运用欧几里得除法，并利用性质8，将求两个正整数的最大公因数转化为求两个较小的非负整数的最大公因数。c) 反复运用欧几里得除法（即广义欧几里得除法），将求两个正整数的最大公因数转化为求0与一个正整数的最大公因数。d) 利用性质7，求出0与正整数的最大公因数，即为欲求的最大公因数。（3） 算法：已知ab0S1 求q及r，使 abqrS2 若r0。则 令db；输出d；结束 否则 令ab；br；转S1 （4） 算法的复杂度：设ab0，则求(a,b)过程中的除法次数<22（5） 例（见后）(五) 斯泰因（St

19、ein）算法（1） 理论依据：性质11及（a，b）（ab，b）（2） 算法：设a0，b>0，输出 d（a，b）S1 k0S2 若a、b均为偶数，则 令aa/2；bb/2；kk1；转S2 否则转 S3S3 若b是偶数，则 ab否则转S4S4 若a是偶数，则 令aa/2； 转S4否则转S5S5 若ab<0，则ab否则转S6S6 a(ab)/2S7 若a0，则 d；输出d；结束 否则转S4（3） 特点：只用到减法，没有用到除法（除以2在二进制数运算中仅作移位操作）。减运算无疑比除法容易得多。（4） 算法的复杂度：设ab0，则减法次数S（5） 例【例1.3.10】a18，b12算 法abk

20、dS1 k018120S2 若a、b均为偶数，则 aa/2；bb/2；kk1；转S2 ；否则转 S3961S3 若b是偶数，则 ab；否则转S4691S4 若a是偶数，则 aa/2；，转S4；否则转S5391S5 若ab<0，则ab；否则转S6931S6 a(ab)/23311次减法S7 若a0，则 d；输出d；结束 ；否则转S4331S4331S5331S60311次减法S7031d6【例1.3.11】a28，b16算 法abkdS1 k028160S2 若a、b均为偶数，则 aa/2；bb/2；kk1；转S2 ；否则转 S31481S2742S3 若b是偶数，则 ab；否则转S447

21、2S4 若a是偶数，则 aa/2；，转S4；否则转S5272S4172S5 若ab<0，则ab；否则转S6712S6 a(ab)/23121次减法S7 若a0，则 d；输出d；结束 ；否则转S4312S4312S5312S61121次减法S7112S4112S5112S60121次减法S7012d6(六) （a，b）与a、b的关系（1） 【定理1.3.2】设a、b为任意正整数，则存在整数s、t，使得（a，b）satb一般情形：对整数，存在整数，使得（证）直接由展转相除法，反推回去，即得结论。（2） 例【例1.3.12】（3） 【定理1.3.3】整数a、b互素存在整数s、t，使得satb1

22、（证）必要性：由定理1.3.2知成立。充分性：设d(a, b) 且有satb1 。da，dbdsatb1d1(七) 求s、t的算法（1）利用求（a，b）的过程反推【例1.3.13】利用展转相除法求s、t。其中464801·3942370572993·3942316720·(464801·39423)16720·4648019713·39423394325·7057 41381755·70752993·(394235·7057)2993·3942316720·70757057

23、1·4138 29191238·41381755·(70574138 1·2919 1219517·29191238·(41381·2919)2919 2·1219 481204·1219517·(29192·1219)1219 2·481 257109·481204·(12192·481)481 1·257 224109·481204·(12192·481)257 1·224 3314·

24、;22495·(2571·224)224 6·33 2611·3314·(2246·33)33 1·26 732·2611·(331·26)26 3·7 52·73·(263·7)3·2611·77 1·5 252·(71·5)2·73·55 2·2 1152·22 2·1所以 116720·4648019713·39423或 1（167

25、2039423）·46480（4468019713）·3942322703·4648026767·39423所以：s16720，t19713（2）取最小绝对余数2 2·17 3·21173·233 5·7273·（335·7）224 7·3373·3314（2247·33）481 2·2243314·22495（4812·224）1219 3·48122495·481204（12194813·481）291

26、9 2·1219481204·1219517（29192·1219）7075 2·29191219517·29191238（70572·2919）394326·705729191238·70572993（394236·7057）464801·3942370572993·3942316720（464801·39423）15720·4548019713·39423所以 116720·4648019713·39423或 1（167203942

27、3）·46480（4468019713）·3942322703·4648026767·39423所以：s22703，t26767（3）算法（4）基于展转相除法：求d（a，b）和s、t，使得dsatbS1 1；0；0；1S2 做除法得 abqrS3 若r0，则db； s； t； 输出d、s、t； 结束 S4 ab； br； t； q·； t； t； q·； t； 转S2【例1.3.14】a132，b108算 法abqrS1 1；0；0；11321081001S2 做除法得 abqr1321081001124S3 若r0，则db；s；t；

28、输出d、s、t；结束 1321081001124S4 ab；br；t；x2q·；t；t；q·；t；转S2108240111124S2108240111412S3 r0108240111412S424121415412S22412141520S3 r02412141520输出 db12，s4，t5即 124×1325×108（5）基于斯泰因算法：S1 k0； F0；S2 若a、b均为偶数，则 aa/2； bb/2； kk1； 转S2 否则转 S3S3 若b为偶数，则 ab； F1 否则转S4S4 Aa； Bb； 1；0；0；1S5 若a是偶数，则 为偶数，

29、转S6；否则转S7否则转S8S6 aa/2； /2； /2； 转S5 S7 若，则 ； ； 转S6 否则 ； ； 转S6 S8 若a<b，则 ab， S9 aab； ； S10 若a0，则 若F1则转S11，否则转S12 否则转S5。S11 S12 d; s； t； 输出结果； 结束。【例1.3.15】a132，b108算 法abABkFS113210800S2665410S2332720S433273327100120S5S8S96273327101120S10S5S7627332726032120S6327332713016120S5S827301311620S92431313151

30、620S10S5S72431413181620S612371391620S5S71232013241620S661012S5S6356S5S8S90333271813221620S10S1212; s13；t16即 1213×13216×108说明：与用展转相除法所得结果不同，说明s、t不唯一。例如 12（10813）×132（16132）×108（加减108×132）95×132（116）×108【例1.3.16】a288，b158(八) 其它性质（14） 设a、b是不全为零的整数（i）若m为任一正整数，则（am，bm）(

31、a，b)m（ii）若非零整数d满足da，db，则。特别地1 （*）（证）（i）由定理1.3.2， d(a，b) 存在s，t使得satbd s(am)t(bm)dm dm （am，bm），即（am，bm）(a，b)m（ii）由（i），对a, b的任何公因数d，都有（a，b）特别地，取d(a，b)，即得（*）式。【例1.3.17】a11×200306，b23×20036，计算(a，b)。 （解）（11×200306，23×20036）20036（11，23）20036（15） 设为整数，且0，令，则。应用：（证）用归纳法【例1.3.18】计算最大公因数（12

32、0，150，210，35）。（解）（120，150）（120，30）30（30，210）30（30，35）5故（120，150，210，35）5即 （120，150，210，35）（30，210），35）（30，35）5或（120，150，210，35）（(120，150)，(210，35)）(30,35) 5(九) 应用【例1.3.19】设a、b式是两个正整数，则1和1互素 a和b互素。（证明见后，需要先证两个引理）【引理1】设a、b是两个正整数，则1被1除的最小正余数是1，其中r是a被b除的正余数。（证）若ab，则ra，结论显然。设ab，由欧几里得除法，有abqr， 1rb从而 1说明：改

33、为最小非负余数，结论也成立。（由此还知，(1)(1) ba）【例1.3.20】a10，b6，则11023，163，从而1023÷631615 或 1(1)16(1)【引理2】设a、b是两个正整数，则1和1的最大公因数是1。（证）由展转相除法及引理1即得。即(1，1) (1，1) (1，0) 1【例1.3.21】(1023，63)(63，15)(15，3)(3，0)0即 (1，1)(1，1) (1，1) (1，0)11（证例1.3.19）由引理2，（1，1）1而11 （a，b）1，即a和b互素。（例1.3.19：设a、b式是两个正整数，则1和1互素 a和b互素）。1.4 整除的进一步性

34、质及最小公倍数(一) 最大公因数性质性质（1） 设a，b，c是三个整数，且b0，c0，若（a，c）1，则（ab，c）（b，c）（证）记d(ab，c)，e(b，c)由eb，ec知eab，ec，再由等价定义知ed。反之，由（a，c）1知存在整数s、t，使得satc1两边同乘以b得 s(ab)(tb)cb而 dab，dc，故ds(ab)(tb)cb，从而de所以 de推论 设a，b，c是三个整数， 且c0， 若cab，且(a，c)1，则cb。（证）cab c(ab，c) (b，c) cb性质（2） 设，c为整数，若1（1in），则1（证）用归纳法。n2时，就是性质（1）。设n1时结论成立，即 1对于

35、n，由1和1及性质（1）知1(二) 整除的进一步性质（8） 设p为素数，若pab，则pa或pb。（证）若pa (p，a)1，再由推论即知pb。反之，若pb (p，b)1，再由推论即知pa。一般情形 设是整数，p是素数，若p，则p一定整除某个。反例：p不是素数的情况。例如p6，a8，b9。尽管672，但却有68，且69。(三) 最小公倍数【定义1.4.1】设为整数，若m是这些数的倍数，则称m为这n个数的一个公倍数，所有公倍数中最小的正整数叫做最小公倍数，记作。等价定义： m （i）（1in）（ii）若（1in），则注：公倍数有无穷多，公因数只有有限个。【例1.4.1】整数14和21的公倍数为&#

36、177;42，±84，最小公倍数14，2142。其公因数则为±1，±7(四) 性质（1） 设a 、b是两个互素正整数，那么（i） am， bm，则 abm；（ii） a，b ab（证）（i）设若am，则mak。又bm，即bak。而（a，b）1，故bk，即kbt，mabt，从而abm。（ii）首先ab是a 、b的公倍数。其次由（i）和等价定义知ab是最小公倍数。（2） 设a 、b是两个正整数，则（i） 若am， bm，则 a，bm；（ii） a，b 。 （求a，b的方法二（方法一是另一定义）一般情形：设为正整数，若每个（1in），则m（证）（ii）令d（a，b），则

37、1。由性质（1）。即 dd又知对任何整数t>0，有ta, bta, tb，从而有a，bd（i）am， bm ， （3） 设为整数，令，则。应用：【例1.4.2】求最小公倍数120，150，210，35。（解）120，150600600，21042004200，354200故120，150，210，354200即 120，150，210，35120，150，210，35 600，210，354200，3542001.5 算术基本定理(一) 整数分解（1） 算术基本定理【定理1.5.1】（算术基本定理）任一整数n1都可以表示成素数的乘积。且在不考虑乘积顺序的情况下，该表达式是唯一的。即， （证）存在性：归纳法唯一性：【例1.5.1】写出整数45，49，100，128的因数分解式（解）由定理1.5.1453·3·5497·71002·2·5·