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

第 1 章 整数的可除性内容1. 整除性2. 公因数、最大公因数3. 辗转相除法（欧几里得除法）4. 算术基本定理要点培养对数论问题的认识及证明问题的思路《数论》从研究整数开始，叫“整数论”经进一步发展，叫做“数论”确切地说，数论是研究整数性质的学科自然数（正整数）负整数0（统称整数）算术运算：加、减、乘、除（四则运算）加法、减法和乘法在整数范围内可以毫无阻碍地进行但整数之间的除法在整数范围内并不一定能够无阻碍地进行《数论算法》主要从应用角度出发，研究数论问题中实用的方法和技术1.1 整除的概念 欧几里得除法(一) 整除概念【定义1.1.1】 设a, b∈Z（整数集合），b≠0，如果存在q∈Z，使得a＝bq，则称b整除a或a可被b整除，记作b│a，且称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的所有因数例：设 a＝6，则有（1） 当b＝3时，q＝2＝6/3（2） 当b＝1, 2, 3, 6,－1,－2,－3,－6时有－b＝－1,－2,－3,－6, 1, 2, 3, 6（3） 当b＝1, 2, 3, 6, －1,－2,－3,－6时有a/b＝6, 3, 2, 1, －6,－3,－2,－1【特例】：（1） 0是任何非零整数的倍数；（2） 1是任何整数的因数；（3） 任何非零整数a是其自身的倍数，也是其自身的因数。

二) 性质（1） 设，则 │证） a＝bq －a＝q(－b) 其余类推例1.1.1】30的所有因数：1，2，3，5，6，15，30（2） 传递性：，（证）且 b＝c，a＝b a＝c c│a3） ，，则（4） ，，则对任意整数s、t，有推广：（5） 若，，则a＝b（证） a＝b b＝a a＝ ＝1 ＝1（6） （c≠0）（7） 若，则 ≤(三) 例【例1.1.2】证明：若且，则证） 已知 即m＝7q所以 n＝3(7q)＝21q 例1.1.3】设证） 又 ＝(an＋n)－an＝n，即（由a＝2t－1知2t＝a＋1，从而2tn＝an＋n）【例1.1.4】设a, b是两个给定的非零整数，且有整数x, y，使得证明：若且，则（证） 由且 ＝n(ax＋by)，即注意到，由此也证明了例1.1.2例1.1.5】设是整系数多项式若，则（证）由及＝ （k＝1, 2, …, n）∴ 应用：若，那么例：设，判断7能否整除因 ＝7q＋4，故只需判断：＝＝3082？答：不能(四) 素数（1） 定义（素数与合数）设整数p≠0, 1如果它除了显然约数1, p外没有其它的约数，那么，就称为素数（或质数、不可约数）。

若a≠0, 1，且不是素数，则称为合数约定：素数一般指正整数2） 性质（a） 最小正因数必是素数（b） n是正整数，当2≤p≤且pn，则n是素数c） 素数有无穷多证）（c）：用反证法假设只有有限个素数：构造则 且a≠（i＝1, 2, …, k）∴ a必是合数 存在素数p，使得 由假设知p等于某个一定整除但素数，矛盾因此，假设是错误的，即素数必有无穷多个性质（b）的应用：快速判断素数扩展：设是全体素数按大小顺序排成的序列，以及直接计算可得：， ， ， ， ， ， ，， ，前五个是素数，后五个是合数，但都有一个比更大的素因数未解决的问题：至今还不知道是否有无穷多个k使是素数，也不知道是否有无穷多个k使是合数五) 欧几里德除法也叫带余数除法、除法算法初等数论的证明中最重要、最基本、最常用的工具之一1） 欧几里德除法：设a, b是两个给定的整数，b≠0那么，一定存在唯一的一对整数q与r，满足, 约定：b>0上式可表为, （2）（2） 存在性当时，可取，r＝0当ba时，考虑集合＝{……，－3b，－2b，－b，0，b，2b，3b，……}将实数分为长度为b的区间，a必落在某区间内，即存在整数q，使得qb≤a＜(q＋1)b令r＝a－bq，则有, （3） 唯一性设有也满足（2）式，即 必有 当q≠时有 ≥b，矛盾，故必有，。

4） 推论：的充要条件是r＝0当a＝qb＋r时, 有当满足时，就有 r＝05） 一般形式设a, b是两个给定的整数，，则对任意整数c，一定存在唯一的一对整数q与r，满足, （3）此外，的充要条件是例：a＝100，b＝30，c＝10，则10≤r＜40，即100＝3*30＋10若c＝35，则35≤r＜65，即100＝2*30＋40若c＝－50，则－50≤r＜－20，即100＝5*30＋(－50)(六) 不完全商和余数【定义1.1.2】设a＝bq＋r（），称q为a被b除所得的不完全商，称r为a被b除所得的余数推论】 b│a的充要条件是a被b除所得的余数r＝0余数的分类：1． 最小非负余数 c＝0，0≤r＜b2． 最小正余数 c＝1，1≤r≤b3． 最大非正余数 c＝－b＋1，－b＋1≤r≤04． 最大负余数 c＝－b，－b≤r＜05． 最小绝对余数 －b/2≤r＜b/2或－b/2＜r≤b/2(七) 下整数与上整数【定义1.1.3】 设x是一个实数，称为下整数函数，其值为不大于x的最大整数即x满足≤x＜＋1（原定义为：设x是一个实数，称x的整数部分为小于或等于x的最大整数，记为）上整数函数：表示不小于x的最小整数。

即－1＜x≤≤x≤四舍五入函数：函数是将x四舍五入的结果说明 当a＝qb＋r（0≤r

例1.3.1】 求最大公因数（12, 18），（6, 10, -15），（n, n＋1）解）（用定义求）a1＝12，a2＝18，故其公因数是1，2，3，6，最大公因数是6a1＝6，a2＝10，a3＝－15，它们的公约数是1，且最大公因数(6, 10,－15)＝1小结论：任何n和n＋1的公约数都是1二) 性质（1） （a）＝ （2） （a，b）＝（b，a）一般情形＝其中是1，2，…，n的一个全排列3） 设a，b为正整数，若b│a，则（a，b）＝b一般：为整数且≠0，│（i＝2，3，…，n），则＝＝＝＝（）＝【例1.3.2】求(6, －12, 42)，(21, 56, －7)（解）因为6│－12，6│42，所以(6, －12, 42)＝(6, －12)＝(6, 12)＝6又知－7│21，－7│56，故 (21, 56, －7)＝7（4） 设p为素数，a为整数，若pa，则p与a互素证）设d＝（p，a），则d│a，d│p但p为素数，故d＝1或p若d＝p，则由d│a知p│a，与假设矛盾故d＝1，即(p, a)＝1（5） 设是n个不全为零的整数，则（i）与的公因数相同ii）()＝（证）由d│知d│，反之，若d│，则必有d│，故（i）成立。

由（i）立得（ii）6） 设a、b为正整数，则＝（证）是性质（5）中（ii）的特例一般情形：a、b为整数，则＝＝或均为整数，则＝＝＝＝（7） 设整数b＞0，则（0，b）＝b一般形式：b≠0，则（0，b）＝（8） 设a，b，c是三个不全为零的整数，a＝bq＋c，其中q是整数，则（a，b）＝（b，c）（证）设d＝（a，b），e＝（b，c）则由d│a，d│b知d│a－bq＝c知d为c的因数，从而d≤e同理可知e≤d，故d＝e意义：是快速求最大公因数d＝(a, b)的算法的理论基础应用：设a，b＞0且a＞b，a＝bq＋c，则 (a，b)＝(a－bq，b)＝(c，b)＝(b，c)【例1.3.3】计算（389, －189）和（8877，9988）（解）由性质8知（389，－189）＝（389，189）＝（389－1892，189）＝（11，189）＝（189，11）＝（189－1117，11）＝（11，2）＝1（注：本例大数在前，一般可不考虑两个数的顺序）（8877，9988）＝（8877，9988－88771）＝（8877，1111）＝（8877－11117，1111）＝（1100，1111）＝（1111，11）＝（0，11）＝11（9） 对任意的整数x，y，有推广：＝＝＝＝ ＝＝＝……应用：化简计算过程【例1.3.4】计算(51，809，17)。

解）(51，809，17)＝(173，809，17)＝(809，17)一般情形： ＝＝ ＝…… （1≤i，j≤n）（10） 对任意整数x，有＝＝ ＝＝…＝注：性质（8）的一般情形证）设d＝(a，b)，e＝(a, b＋ax)，f＝(a＋by, b) d│a，d│bd│b＋axd│e，即d≤ee│a，e│b＋axe│（b＋ax）－ax＝be│d，即e≤d，故d＝e应用：从右向左化简例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）＝＝。