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

主要内容:1．1.整除的概念1．2.带余数除法1．3.最大公因数的理论与性质1．4.最小公倍数的理论与性质1．5.辗转相除法1．6.素数与合数1．7.算术基本定理1．8.高斯函数[x]与{x}及其应用1.1.1 整除的定义与性质1.整除的定义定义设a，b∈Z，b≠ 0，若存在整数c，使得a = bc成立，则称a被b整除（或b整除a），并称a是b的倍数，b是a的约数（因数或除数），记为b∣a；如果不存在整数c使得a = bc成立，则称a不能被b整除，记为b|/a。

在整除的定义中应特别注意：（1）0不整除任何整数（即0不能作除数），但任何非零数整除0；在记号“b∣a”中蕴含着b≠ 0成立。

（2）显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数（平凡因子），a的除±1，±a外的约数称为非平凡约数（或真因数）。

（3）能被2整除的整数称为偶数，不能被2整除的整数称为奇数。

若整数a ≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

2.整除的性质定理1.1.1 设,,a b c ,m,n 是整数,下面的结论成立：(ⅰ) a ∣b ，b ∣c ⇒ a ∣c （整除的传递性）；(ⅱ) a ∣b ⇔ ±a ∣±b ，即a ∣b ⇔ |a |∣|b |;m ∣a , n ∣b ⇒ mn ∣ab ；(ⅲ) 若b ∣a ，且b ∣c ⇒ b ∣(ka+lc)（其中k , l 是任意的整数）；一般地，若m ∣a i ，i = 1, 2, , n ⇒ m ∣（q 1a 1 + q 2a 2 + + q n a n ）， 此处q i （i = 1, 2, , n ）是任意的整数；(ⅳ) b ∣a ⇔ bc ∣ac ，此处c 是任意非零的整数；(ⅴ) 若b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；若b ∣a ，且|a | < |b | ⇒ a = 0；若b ∣a ，且a ∣b ，a >0, b>0, 则a =b.证明 (ⅰ)由整除定义及|a b ，|,b c 知: 存在两个整数12,k k 使得:12,b ak c bk ==, 因此12()c k k a =, 由于12k k 是整数, 故 |a c .(ⅱ) — (ⅳ)的结论类似可证. 证毕.注 为了证明“|b a ”，最为基本的手法是将a 分解为b 与某个整数之积，即a bc =，其中c 是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如：（Ⅰ）若n 是正整数，则1221()();n n n n n n a b a b a a b ab b -----=-++++（Ⅱ）若n 是正奇数，则在上式中以（b -）代换b 得:1221()().n n n n n n a b a b a a b ab b ----+=+-+-+例1 证明十进制整数5001001个能被十进制整数1001整除.证明 由分解因式公式(Ⅱ),有500513171*********=+=+个（）33163153101[(10)10101],=+-+-+（）（）所以, 31011001+=能整除5001001个.证毕想一想:此题目能变形推广吗?推广后的一般形式是什么?例2 若n 是正奇数，则8∣（n 2 - 1）.证明 设n = 2k + 1，()k Z ∈，则 n 2 - 1= (2k + 1)2 - 1 = 4k (k + 1).由于k 和k + 1中必有一个是偶数，所以8∣（n 2 - 1）. 证毕注 由此得到一个重要且常用的结论：“任何奇数的平方与1的差都能被8整除”.诸如此类的还有，“任何整数的平方被4除的余数为0或1，被3除的余数为0或1; 任何整数的立方被9除的余数为 0，1或8”等，解题后可及时总结归纳, 并灵活运用这些性质.例3 设n 是奇数，则16∣(n 4 + 4n 2 + 11).解 因为 n 4 + 4n 2 + 11 = (n 2 - 1)(n 2 + 5) + 16.由于n 是奇数,有8∣(n 2 - 1)，且2∣(n 2 + 5),故16∣(n 2 - 1)(n 2 + 5).从而16∣(n 2 - 1)(n 2 + 5)+16,即16∣(n 4 + 4n 2 + 11).例4 设,m n 为正整数，且0m n >≥, 证明: 22(21)|(21)n m +-. 证明 由于0m n >≥, 故10m n --≥. 于是:112222(2)m n m n +--=在公式(Ⅰ)中，令 122n a +=, 1b =，则:11111111221222222222(2)(2111[(2)(1)2)2]n m n n m n m m n n n n +--+--+++------++=+=+-所以 122(21)|(21),n m +-- 又 1222(221(21),1)n n n ++-=-因此 122(21)|(21).n n ++-由定理1.1.1中 (ⅰ),即整除的传递性知：22(21)|(2).1n m+- 证毕． 注1 在此例中，直接证明“22(21)|(21)n m +-”不易入手，因此尝试选择适当的“中间量（1221n +-）”，使之满足定理1.1.1中 (ⅰ)的条件，再利用整除的传递性导出所要的结论.注2 在此例中，形如“221n n F =+()n N ∈”的数称为费马数.当0m n >≥时, 费马数满足: |(2)n m F F -，即存在整数t ，使得2m n F t F -=⋅.例5 设正整数n 的十进制表示为: 10(09,0,0)k i k n a a a a i k a =≤≤≤≤≠，且110()k k S n a a a a -=++++，证明：9|n 的充要条件是9|()S n .证明：由于101010k k n a a a =⨯++⨯+,110()k k S n a a a a -=++++，1()(101)(101)(101)k i k i n S n a a a ∴-=-+-++-, 对于所有的0,i k ≤≤ 有9|(101),i -由整除的性质知上式右端k 个加项中每一项都是9的倍数，由定理1.1.1之(ⅲ)知它们的和也被9整除，即9|(()),n S n - 从而 9|9|()n S n ⇔. 证毕.注 两个十进制正整数,其中一个被另一个正整数整除的条件，称为“整除的数字特征”.例5得出十进制正整数n 被9整除的数字特征是:“9整除n 的各位数字之和”.下面例题6得出十进制正整数n 被11整除的数字特征是:“11整除n 的各位数字的正负交错之和”.例6 设正整数n 的十进制表示为10(09,0)k i k n a a a a a =≤≤≠，n 的个位为起始数字的正负交错和 01()(1)k k T n a a a =-++-，证明：“11|n ”的充分必要条件是“11|()T n ”.证明 由于 101010k k n a a a =⨯++⨯+, 01()(1)k k T n a a a =-++-，1()(10(1))(10(1))(101)k k i i k i n T n a a a ∴-=--++--+++ 当i 为偶数时， 10(1)9999i i --= ，其中有偶数个9，显然它是11的倍数；当i 为奇数时，10(1)101(101)11()i i i s s s z --=+=+=∈， 它也是11的倍数,故总有11|(10(1)),(0).i i i k --≤≤ 即11|(())n T n -成立. 从而11|11|().n T n ⇔习题1.11．设n 是整数，则3|(1)(21)n n n ++. 2. 设正整数n 的十进制表示为10(09,0,0)k i k n a a a a i k a =≤≤≤≤≠，n 的个位为起始数字的正、负交错的和 01()(1)k k T n a a a =-++-，证明：“11|n ”的充分必要条件是“11|()T n ”.3. 若10个男孩和n 个女孩共买了282n n ++本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?4．证明一个整数a 若不能被2整除，也不能被3整除, 则223a +必能被24整除.5. 已知整数,,,m n p q 适合: (m - p ) ∣(mn + pq )，证明:(m - p )∣(mq + np ).对任意两个整数,(0)a b b ≠，a 未必能被b 整除. 为了能在整数范围内研究除法，引入整数的除法算法——带余数除法，它是初等数论证明中最重要、最基本、最常用的工具. 本节中，我们将介绍带余数除法及其简单应用. 我们约定, 以Z 表示所有整数的集合，N 表示所有正整数的集合. 除特别声明外，在涉及到带余数除法时总假定除数是正整数.1. 带余数除法定理1.2.1 (带余数除法) 设a 与b 是两个整数，b>0，则存在惟一的一对整数q 和r ，使得:a = bq + r ，0 ≤ r <b . (2)若a = bq + r (0 ≤ r < b ), 则|b a 的充分必要条件是0r =.证明: 存在性作整数序列: ,3,2,,0,,2,3,b b b b b b ---则a 必在上述序列的某两项之间,即存在一个整数q ,使得(1)qb a q b ≤<+成立. 令a qb r -=,则,a qb r =+而0.r b ≤<1.1.2 带余数除法惟一性 假设11,q r 是满足(2) 的两个整数，即 111(0),a bq r r b =+≤< 则 11a bq r bq r =+=+于是 1111()||||b q q r r b q q r r -=-⇒-=-(3)由上式推出: 1||b r r -,由于 110,0||r r b r r b <<⇒≤-<因此必有1||0r r -=,即1r r =，代入式(3)得 1q q =，惟一性得证.若a bq r =+(0)r b ≤<，则 ||,b a b r ⇔ 又 0r b ≤<, 则 |0.b r r ⇔=故|0.b a r ⇔= 证毕 注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.定义：在式a = bq + r （0 ≤ r < b ）中，q 称为a 被b 除的不完全商，r 称为a 被b 除的余数, 也称为最小非负剩余.带余数除法是一个重要的工具，数论的许多基本性质都是建立在带余数除法基础之上的.例1 当 15,225b a ==时有 1701022515,175,;r q <===⨯+ 当 15,417b a ==时有 1241715,15,;2072712q r <<===⨯+ 当 15,81b a ==-时, 有 0(6)8115,15,9;96q r --<=+<=-=⨯且有 (6)8115,(5)5;60,q r =--<=⨯-=--+ 此处{0,1,2,,151}r ∉-，这时的余数r 不是最小非负剩余。

第一章整数的可除性整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的q，使得成立，则称a能被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b∣a；如果不存在整数q使得a = bq成立，则称a不被b整除，记为显然每个非零整数a称这四个数为a的平凡约数，a下面的结论成立：∣a⇔±b∣±a；(ⅱ) c ∣b，b∣a⇒c∣a；(ⅲ) b∣a i，i = 1, 2, …, n⇒b∣a1q1+a2q2+…+a n q n，此处q i（i = 1, 2, , n）是任意的整数；(ⅳ) b∣a ⇒bc∣ac，此处c是任意的非零整数；(ⅴ) b∣a，a≠ 0 ⇒|b|≤|a|；b∣a且|a|<|b|⇒a = 0。

) 设a 与b 是两个整数，b > 0，则存在q 和r ，使得a = bq + r ，0 ≤ r <b (2) 成立且q 。

中的q 叫做a 被b 除所得的不完全商，r 叫做a 被例1 若1n >，且111n n -+ 求n222x y z +=的整数解能否全是奇数？为什300”位于哪个字母的下面A B C D E F G1 2 3 45 6 78 9 10 1112 13 1415 16 17 ……. 解：观察可以发现两行7个数组成一组故300=7×42+6与6同在字母D 的下面例4 a 除以b 商为c ，余数为r ，则am 除以bm 商为 ， 余数为 。

m N +∈某整数除以3余2，除以4余1，该整数除以12，余 ？三、整除的特征从正整数121n n N a a a a a a -=的末位a 起向左每k 个数码分为一节，最后剩下若有不足k 个数码的也为一节，记为()1()(),,,k k t k A A A并记()1()()()k k k t k S N A A A =+++----数节和1()1()2()()()(1)t kk k k t k S N A A A A -'=-++-----数节代数和 1、设d 是10k 的约数，则()k d N d A ⇔推论：能被2或5整除的数的特征是：这个数的末一位数能被2或5整除。

整数的整除性与同余（教案）教学内容 整除与同余教学目标 1 让学生初步学习整除与同余的概念及基本性质;2 能够简单的应用整除与同余的知识处理一些初等数论问题.教学过程一、整数的整除性1、整除的定义：对于两个整数a 、b （b ≠0），若存在一个整数m ，使得b m a ⋅=成立，则称b 整除a ，或a 被b 整除，记作b|a.2、整除的性质1）若b|a,则对于任意非0整数m 有bm|am;2) 若b|a ，c|b ，则c|a3) 若b|ac ，而（a ，b ）=1（（a ，b ）=1表示a 、b 互质，则b|c ；4) 若b|ac ，而b 为质数，则b|a ，或b|c ；5) 若c|a ，c|b ，则c|（ma+nb ），其中m 、n 为任意整数（这一性质还可以推广到更多项的和）6）连续整数之积的性质任意两个连续整数之积必定是一个奇数与一个偶数之一积，因此一定可被2整除；任意三个连续整数之中至少有一个偶数且至少有一个是3的倍数，所以它们之积一定可以被2整除，也可被3整除，所以也可以被2×3=6整除例1 （1987年北京初二数学竞赛题）x ，y ，z 均为整数，若11｜（7x+2y-5z ），求证：11｜（3x-7y+12z ）。

证明∵4(3x -7y+12z)+3(7x+2y-5z)=11(3x-2y+3z)而 11｜11(3x-2y+3z),且 11｜(7x+2y-5z),∴ 11｜4(3x-7y+12z)又 (11,4)=1 ∴ 11｜(3x-7y+12z)例2（1980年加拿大竞赛题）设72｜b 679a 试求a,b 的值。

解：∵72=8×9，且（8，9）=1，∴只需讨论8、9都整除b 679a 时a,b 的值。

若8｜b 679a ，则8｜b 79，由除法可得ｂ＝２若9｜b 679a ，则9｜（a+6+7+9+2），得a=3例3（1956年北京竞赛题）证明：1n 21n 23n 23-++对任何整数n 都为整数，且用3除时余2。

七年级数学《数的整除性》数论初步教案一、教学目标1. 理解数的整除性的概念和相关性质；2. 能够运用数的整除性进行问题的求解；3. 培养学生的逻辑思维和分析问题的能力。

二、教学重点和难点1. 整除性的概念和基本性质的理解；2. 运用整除性解决问题的能力。

三、教学准备1. 教材：教科书、练习册；2. 工具：黑板、彩色粉笔。

四、教学过程第一步：导入新知识（5分钟）1. 引入问题：小明去超市买了一些苹果，他把苹果分成了3堆和4堆，苹果的总数不变。

你知道这个数字是多少吗？2. 提问：你觉得有哪些整数可以满足这个条件呢？第二步：引入整除性这一概念（10分钟）1. 教师解释：我们把刚才的问题转换一下，假设小明一共买了f个苹果，那么f应该能被3整除，也能被4整除。

这里，我们就引入了“整除”的概念。

2. 提问：你们能给出整除的定义吗？3. 学生回答：如果一个数a能被一个非零整数b整除，那么就说a 能被b整除，b是a的约数。

第三步：整除性的判定方法（15分钟）1. 教师提供整除性的判定方法：a. 若a除以b的余数为0，则a能被b整除；b. 若a能被b整除，则a是b的倍数。

2. 举例说明：例如，6能被2整除，因为6 ÷ 2 = 3 余 0，所以6是2的倍数。

第四步：整除性的性质（20分钟）1. 整除的传递性：若a能被b整除，b能被c整除，那么a能被c整除。

2. 举例说明：例如，6能被2整除，2能够被1整除，所以6能被1整除。

3. 提问：你们还能举出其他整除的例子吗？第五步：整除性的应用（20分钟）1. 教师提供一些实际生活中的问题，让学生运用整除性进行求解，例如：a. 一个教室有48个学生，把学生分成若干组，每组学生人数相同，最多能分成几组？b. 物业要把58个花盆摆放在教学楼前的花坛里，每个花坛要盛放相同数量的花盆，最多能放几个花坛？2. 学生进行小组讨论并展示解题过程和答案。

第六步：小结与拓展（10分钟）1. 教师对本节课的内容进行小结，并强调数的整除性在解决问题中的重要性。

第 1 章整数的可除性《数论》从研究整数开始，叫“整数论”。

经进一步发展，叫做“数论”。

确切地说，数论是研究整数性质的学科。

自然数（正整数）→负整数→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整除，记作b a。

◆ 说明（1） q 也是a 的因数，并将q 写为a/b 或ba ； （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） 设Z b a ∈,，则a b a b a b |||-⇔-⇔a b --⇔| ⇔b │a 。

（证） ⇔a b | a ＝bq ⇔ －a ＝q(－b) ⇔a b --| 其余类推。

【例1.1.1】30的所有因数：±1，±2，±3，±5，±6，±15，±30（2） 传递性：b c |，a b |⇒a c |（证）b c |且a b | ⇒ b ＝c 1q ，a ＝b 2q⇒ a ＝c 1q 2q ⇒c │a 。

数的整除性定义 设,a b Z ∈，0b ≠，如果存在c Z ∈，使得a bc =成立，则称b 整除a ，记作b a ；不然，则称b 不整除a ，记作|b a /．每个非零整数a 都有约数1，1-，a ，a -，这4个数称为a 的平凡约数，a 的其他的约数称为非平凡约数．性质 （1）a b a b ⇒±±； （2）a b ，b c a c ⇒； （3）1122(1,2,,)i k k b a i k b a x a x a x =⇒+++（其中i x 是任意整数）； （4）b a bc ac ⇒（其中c 是任意的非零整数）； （5）b a ，0a b a ≠⇒≤； （6）b a ，0a b a <⇒=．1.已知,,,,a b c d t Z ∈，且10t a b -，10t c d -．求证：t ad bc -．2.设,a b 是两个给定的非零整数，且有整数,x y ，使得1ax by +=．求证：若a n ，b n ，则ab n ．3.已知,,,a b c d Z ∈，且a c ab cd -+．求证：a c ad bc -+．4.证明：设a 是奇数，若2a n ，则a n ．5.证明：设1110()n n n n f x a x a x a x a --=++++是整系数多项式，若d b c -，则()()d f b f c -．6.已知数列1，4，8，10，16，19，21，25，30，43中，相邻若干个数之和能被11整除的数组共有多少个？7.已知6a b c ++，求证：3336a b c ++．8.已知n 为大于2的整数，求证：5312054n n n -+．素数与合数定义 若整数0,1a ≠±，并且只有约数1±，a ±，则称a 是素数（或质数）；不然，则称a 为合数．注意：①素数也称为不可约数，它总是指正整数；②由定义知，全体整数可以分为1、素数、合数三大类．定理 （1）任何大于1的整数a 都至少有一个素约数；（2）如果a 是大于1的正整数，则a 的大于1的最小约数必为素数；（3）任何大于1的合数a（4）素数有无穷多个； （5）设12{,,,}k A d d d =是n 的所有约数的集合，则12{,,,}kn nnB d d d =也是n 的所有约数的集合．1.若n 是奇数，则281n -．2.以()d n 表示n 的正约数的个数，例如(1)1d =，(2)(3)2d d ==，(4)3d =等等，问20151()k d k =∑是否为偶数？3.设1(1,2,,)a Z i n ∈=，且120n a a a +++=，12n a a a n =，则4n ．4.求三个素数，使得它们的积为和的5倍．5.若n 是合数，则n 位数111n 个也是合数．6.设a 是自然数，问4239a a -+是素数还是合数？7.设p 是n 的最小素约数，11,1n pn n =>．证明：若p 1n 是素数． 8.证明：存在无穷多个正整数a ，使得4(1,2,)n a n +=对任意正整数n 都是合数．带余除法定理 若,a b 是两个整数，且0b >，则存在两个整数q 及r ，使得(0)r a q b r b =≤<+成立，且q 和r 是唯一的．式子中，q 称为a 被b 除的商，r 称为a 被b 除的余数．1.任给的5个整数中，必有3个数之和能被3整除．2.设01,,,n a a a Z ∈，10()n n f x a x a x a =+++．已知(0)f 与(1)f 都不是3的倍数．证明：若方程()0f x =有整数解，则3(1)f -．3.设223a b +．证明：3a ，且3b ．4.证明：对于任何整数,m n ，等式222(1)2n n m ++=+不可能成立．5.已知n 是整数．证明：3(1)(21)n n n ++．6.证明：形如31n -的数不可能是完全平方数．7.已知2229a b c ++．则229a b -或229b c -或229c a -．8.若00ax by +是形如ax by +（,x y 是任意整数，,a b 是两个不全为零的整数）的数中的最小正数，则00()ax by +|()ax by +，其中,x y 是任意整数．定义 整数12,,,(2)k a a a k ≥，若整数d 是它们中每一个数的因数，那么d 就叫做12,,,k a a a 的一个公约数．整数12,,,k a a a 的公因数中最大的一个叫做最大公因数（或最大公约数），记作12(,,,)k a a a ．若12(,,,)1k a a a =，就说12,,,k a a a 互质或互素；若诸(,)1i j a a =，即12,,,k a a a 中每两个整数都互素，就说它们两两互素．性质 （1）1212(,,,)(,,,)k k a a a a a a =；（2）(,1)1a =，(,0)a a =，(,)a a a =； （3）(,)(,)a b b a =；（4）若p 是素数，a 是整数，则(,)1a p =或p a ； （5）若a pb r =+，则(,)(,)a b b r =． 定理 设,a b 是任意两个不全为零的整数．（1）若m 是任意一个正整数，则(,)(,)am bm a b m =； （2）若δ是,a b 的任意一个公约数，则(,)(,)a b a b δδδ=．特别地，(,)1(,)(,)a ba b a b =． 1.证明：若*n N ∈，则214143n n ++是既约分数．2.设,a b 是整数，且229a ab b ++，则3(,)a b ．3.证明：2121|212n n ++/，n Z ∈．4.证明：若(,4)(,4)2a b ==，则(,4)4a b +=．5.证明：若(,)1a b =，c a b +，则(,)(,)1c a c b ==．6.证明：从任意5个互素的三位数中，总能选出4个数是互素的．定义 整数12,,,n a a a 的公共倍数称为12,,,n a a a 的公倍数，12,,,n a a a 的正公倍数中最小的一个叫做12,,,n a a a 的最小公倍数，记作12[,,,]n a a a ．性质 （1）[,1]a a =，[,]a a a =； （2）[,][,]a b b a =； （3）1212[,,,][,,,]n n a a a a a a =；（4）若a b ，则[,]a b b =．定理 （1）对任意的正整数,a b ，有[,](,)aba b a b =； （2）设,,m a b 是正整数，则[,][,]ma mb m a b =； （3）若12,,,n a a a 是()2n n ≥个正整数，记122[,]a a m =，233[,]m a m =，…，211[,]n n n m a m ---=，1[,]n n n m a m -=，则12[,,,]n n a a a m =．1.设,,a b c 是正整数，则[,,](,,)abca b c ab bc ca =．2.设,a b 是正整数，则[,]()[,]a b a b a b a b +=+．3.设,a b 是正整数，证明：[,](,)a b a b a b =⇔=．4.证明：[,,](,)(,)(,)1a b c abc a b b c c a =⇔===．5.证明：设(,)1m a =，则(,)(,)m ab m b =．6.证明：若0a >，(,)1b c =，则(,)(,)(,)a bc a b a c =．辗转相除法定义 设a 和b 是整数，0b >，依次做带余除法：111(0)a bq r r b =+<<， 12221(0)b rq r r r =+<<，……211(0)n n n n n n r r q r r r ---=+<<， 1111(0)n n n n n r r q r r -+++=+=，且12110n n n b r r r r r -+>>>>>>=，则 111(,)(,)(,)(,)(0,)n n n n n n a b r b r r r r r r -+======，这一组带余除法叫做辗转相除法．定理 （1）若a 和b 是任意两个非零整数，则存在整数,x y ，使得(,)ax by a b +=成立；（2）若a 和b 是任意两个非零整数，则a 与b 互素⇔存在整数,x y ，使得1ax by +=成立．1.求(12345,678)，(169,121)，(1859,1573)-，(221,391,136)．2.求(125,17)，以及,x y 使得12517(125,17)x y +=．算术基本定理定理 （1）设a 是任意一个大于1的整数，则a 的除1以外最小正因数q 是一个素数，并且当a 是合数时，q ≤（2）若p 是一素数，a 是任一整数，则a 能被p 整除或p 与a 互质； （3）设12,,,n a a a 是n 个整数，p 是素数，若12n p a a a ，则p 一定能整除某一个i a ；（4）任何大于1的正整数a 可以写成素数之积，即12n a p p p =，其中诸ip 皆为素数；（5）算术基本定理：任何大于1的正整数a 可以唯一地表示成1212n n a p p p ααα=，其中诸i p 皆为素数，12n p p p <<<，诸i α皆为正整数．我们称1212n n a p p p ααα=是a 的标准分解式．由此可知a 的不同的正约数个数等于12(1)(1)(1)n ααα+++．推论1：设a 是一个大于1的整数，且1212n n a p p p ααα=，(1,2,,)i i n α=是正整数，则a 的正因数d 可以表示成1212n n d p p p βββ=（,1,2,,i i i n αβ≥=）的形式。

初等数论第一讲 整数的可除性（1）一. 数论的简单介绍在数学竞赛中，初等数论的问题是考查的热点之一。

初等数论可以说是最古老的数学分支之一，主要研究整数的性质及其相互关系。

数论的发展有很长的历史，古希腊人对数论的发展做出了重要贡献。

初等数论的知识比较简单，但处理问题方面技巧性比较强。

它所涉及的范围有：整数的可除性，同余理论，不定方程，反证法等。

反证法是解决数论问题常用的方法.二. 本讲内容1.整数的基本性质（1）偶数2n ，奇数21n +或21n -.（n 是整数）（2）奇数与偶数的性质奇数±奇数=偶数；偶数±偶数=偶数；奇数±偶数=奇数；奇数⨯奇数=奇数；偶数 ⨯偶数=偶数；奇数 ⨯偶数=偶数.（3）任何一个正整数n 都可以写成2k n m =⋅的形式， 其中k 为非负整数，m 为奇数.2.整除的性质定义：设,a b 是任意两个整数，其中0b ≠，如果存在一个整数q 使得等式a bq =成立，则称b 整除a ，或a 被b 整除，记作b a .整除的性质：(1).|,|,|;(2).,,(1,2,,),|,|;1(3).,,,|,|.(4).|,||||.|,|,;a b b c a c n a b x Z i n a b a b x i i i i i i a b m Z a b am bm a b a b a b b a a b ∈=∑=∈≤=±若则若且则若且则反之，亦成立；若则因此，若则 (5).,|,|,|;|,|(6).|,12|(1).|,|.(7).a b a c b c ab c a bc a c p p a a a a n i n p a i n p p a p a in ⋅≤≤互质，若则若则；为质数，若则至少有一个，使得特别地，若是质数，且则个连续整数的成积一定能被n ！整除.算术基本定理（正整数的唯一分解定理） 若不计因数的次数，每一个大于1的整数a 都可以唯一分解成质因数乘积的形式.即12121212,,.n n nn a p p p p p p αααααα=⋅<<<其中均为质数，，，为自然数定理：质数的个数是无穷的.三.例题精讲1.证明：2.3. 设a,b,c 是三个互不相等的正整数，求证： 三数中至少有一个能被10整除.3|(1)(21),.n n n n ++！其中是任何正整数21n+若是质数(n>1),证明：n 是2的方幂.333333,,a b ab b c bc c a ca ---4. 4.设n 为自然数，求证： 能被1985整除.5. 5.设p 是大于5的质数，求证：6.设正整数 d 不等于2，5，13.证明：在集合{2,5,13,d}中可以找到两个元素a,b ，使得ab-1不是完全平方数.7.设 是一组数，它们中的每一个都去1或-1，而且 证明： n 必须是4的倍数.3237632855235n n n n A =--+4240|(1)p -12,,,n a a a 123423451230n a a a a a a a a a a a a +++=。

初等数论教案1第一篇：初等数论教案1第二节最大公因数与辗转相除法第三节最小公倍数教学目的：1、掌握最大公因数与最小公倍数性质；2、掌握辗转相除法；3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质教学难点：辗转相除法教学课时：6课时教学过程一、最大公因数1、定义1整数a1, a2, Λ, ak的公共约数称为a1, a2, Λ, ak的公约数.不全为零的整数a1, a2, Λ, ak的公约数中最大的一个叫做a1, a2, Λ, ak的最大公约数（或最大公因数），记为(a1, a2, Λ, ak).注：1、由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数.2、如果(a1, a2, Λ, ak)= 1，则称a1, a2, Λ, ak 是互素的（或互质的）；如果(ai, a j)= 1，1 ≤ i, j ≤ k，i ≠ j，则称a1, a2, Λ, ak是两两互素的（或两两互质的）.显然，a1, a2, Λ, ak两两互素可以推出(a1, a2, Λ, ak)= 1，反之则不然，例如(2, 6, 15)= 1，但(2, 6)= 2.2、定理1下面的等式成立：(ⅰ)(a1, a2, Λ, ak)=(|a1|, |a2|, Λ, |ak|)；(ⅱ)(a, 1)= 1，(a, 0)= |a|，(a, a)= |a|；(ⅲ)(a, b)=(b, a)；(ⅳ)若p是素数，a是整数，则(p, a)= 1或p∣a；(ⅴ)若a = bq + r，则(a, b)=(b, r).证明：(ⅰ)--(ⅳ)留作习题.(ⅴ)由第一节定理1可知，如果d∣a，d∣b，则有d∣r = a - bq，反之，若d∣b，d∣r，则d∣a = bq +r.因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a, b)=(b, r).证毕3、定理2设a1, a2, Λ, ak∈Z，记A = { y；y =∑aixi，xi∈Z，1≤ i ≤ k }.i=1k如果y0是集合A中最小的正数，则y0 =(a1, a2, Λ, ak).证明设d是a1, a2, Λ, ak的一个公约数，则d∣y0，所以d ≤ y0.另一方面，由第一节例2知，y0也是a1, a2, Λ, ak的公约数.因此y0是a1, a2, Λ, ak的公约数中的最大者，即y0 =(a1, a2, Λ, ak).证毕推论1设d是a1, a2, Λ, ak的一个公约数，则d∣(a1, a2, Λ, ak).注：这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数.推论2(ma1, ma2, Λ, mak)= |m|(a1, a2, Λ, ak).推论3记δ =(a1, a2, Λ, ak)，则(aa1a2，Λ,k)= 1，δδδ特别地,(ab,)= 1.(a,b)(a,b)4、定理3(a1, a2, Λ, ak)= 1的充要条件是存在整数x1, x2, Λ, xk，使得a1x1 + a2x2 +Λ+ akxk = 1.(1)证明必要性由定理2得到.充分性若式(1)成立，如果(a1, a2, Λ, ak)= d > 1，那么由d∣ai（1 ≤ i ≤k）推出d∣a1x1 + a2x2 +Λ+ akxk = 1，这是不可能的.所以有(a1, a2, Λ, ak)= 1.证毕5、定理4对于任意的整数a，b，c，下面的结论成立：(ⅰ)由b∣ac及(a, b)= 1可以推出b∣c；(ⅱ)由b∣c，a∣c及(a, b)= 1可以推出ab∣c.证明(ⅰ)若(a, b)= 1，由定理2，存在整数x与y，使得ax + by = 1.因此acx + bcy = c.(2)由上式及b∣ac得到b∣c.结论(ⅰ)得证；(ⅱ)若(a, b)= 1，则存在整数x，y使得式(2)成立.由b∣c与a∣c得到ab∣ac，ab∣bc，再由式(2)得到ab∣c.结论(ⅱ)得证.证毕推论1若(a, b)= 1，则(a, bc)=(a, c).证明设d是a与bc的一个公约数，则d∣a，d∣bc，由式（2）得到，d|c, 即d是a与c的公约数.另一方面，若d是a与c的公约数，则它也是a与bc的公约数.因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a, bc)=(a, c).证毕推论2若(a, bi)= 1，1 ≤ i ≤ n，则(a, b1b2Λbn)= 1.证明留作习题.6、定理5对于任意的n个整数a1, a2, Λ, an，记(a1, a2)= d2，(d2, a3)= d3，Λ，(dn - 2, an - 1)= dn - 1，(dn - 1, an)= dn，则dn =(a1, a2, Λ, an).证明由定理2的推论，我们有dn =(dn - 1, an)⇒ dn∣an，dn∣dn - 1，dn - 1 =(dn - 2, an -1)⇒ dn - 1∣an - 1，dn - 1∣dn - 2，⇒ dn∣an，dn∣an - 1，dn∣dn - 2，dn - 2 =(dn - 3, an - 2)⇒ dn - 2∣an - 2，dn - 2∣dn - 3 ⇒ dn∣an，dn∣an - 1，dn∣an - 2，dn∣dn - 3，ΛΛd2 =(a1, a2)⇒ dn∣an，dn∣an - 1，Λ，dn∣a2，dn∣a1，即dn 是a1, a2, Λ, an的一个公约数.另一方面，对于a1, a2, Λ, an的任何公约数d，由定理2的推论及d2, Λ, dn的定义，依次得出d∣a1，d∣a2 ⇒ d∣d2，d∣d2，d∣a3 ⇒ d∣d3，ΛΛd∣dn - 1，d∣an ⇒ d∣dn，因此dn是a1, a2, Λ, an的公约数中的最大者，即dn =(a1, a2, Λ, an).例1证明：若n是正整数，则21n+414n+3是既约分数.解：由定理1得到(21n + 4, 14n + 3)=(7n + 1, 14n + 3)=(7n + 1, 1)= 1.注：一般地，若(x, y)= 1，那么，对于任意的整数a，b，有(x, y)=(x -ay, y)=(x -ay, y - b(x -ay))=(x -ay,(ab + 1)y - bx)，因此，x-ay(ab+1)y-bx是既约分数.例2证明：121/|n2 + 2n + 12，n∈Z.解：由于121 = 112，n2 + 2n+ 12 =(n + 1)2 + 11，所以，若112∣(n + 1)2 + 11，则11∣(n + 1)2，因此，由定理4的推论1得到11∣n + 1，112∣(n + 1)2.再由式(3)得到112∣11，这是不可能的.所以式(3)不能成立.注：这个例题的一般形式是：设p是素数，a，b是整数，则pk/|(an + b)k + pk - 1c，其中c是不被p整除的任意整数，k是任意的大于1的整数.例3设a，b是整数，且9∣a2 + ab + b2，则3∣(a, b).(3)(4)解：由式(4)得到9∣(a - b)2 + 3ab ⇒ 3∣(a - b)2 + 3ab⇒ 3∣(a - b)2 ⇒ 3∣a - b(5)⇒ 9∣(a - b)2.再由式(4)得到9∣3ab ⇒ 3∣ab.因此，由定理4的推论1，得到3∣a或3∣b.若3∣a，由式(5)得到3∣b；若3∣b，由(5)式也得到3∣a.因此，总有3∣a且3∣b.由定理2的推论推出3∣(a, b).例4设a和b是正整数，b > 2，则2b - 1/|2a + 1.解：(ⅰ)若a < b，且2b - 1∣2a + 1.(6)成立，则2b - 1 ≤ 2a + 1 ⇒ 2b - 2a ≤ 2 ⇒ 2a(2b - a - 1)≤ 2，于是a = 1，b - a = 1，即b = 2，这是不可能的，所以式(6)不成立.(ⅱ)若a = b，且式(6)成立，则由式(6)得到2a - 1∣(2a - 1)+ 2 ⇒ 2a - 1∣2 ⇒ 2a - 1 ≤ 2 ⇒ 2a ≤ 3，于是b = a = 1，这是不可能的，所以式(6)不成立.(ⅲ)若a > b，记a = kb + r，0 ≤ r < b，此时2kb - 1 =(2b - 1)(2(k - 1)b + 2(k - 2)b +Λ+ 1)=(2b - 1)Q，其中Q是整数.所以2a + 1 = 2kb + r + 1 = 2r(2kb - 1 + 1)+ 1 = 2r((2b - 1)Q + 1)+1 =(2b - 1)Q '+(2r + 1)，其中Q'是整数.因此2b - 1∣2a + 1 ⇒ 2b - 1∣2r + 1，在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立.综上证得2b - 1/|2a + 1.二、最小公倍数1、定义1整数a1, a2, Λ, ak的公共倍数称为a1, a2, Λ, ak的公倍数.a1, a2, Λ, ak的正公倍数中的最小的一个叫做a1, a2, Λ, ak的最小公倍数，记为[a1, a2, Λ, ak].2、定理1下面的等式成立：(ⅰ)[a, 1] = |a|，[a, a] = |a|；(ⅱ)[a, b] = [b, a]；(ⅲ)[a1, a2, Λ, ak] = [|a1|, |a2| Λ, |ak|]；(ⅳ)若a∣b，则[a, b] = |b|.证明留作习题.由定理1中的结论(ⅲ)可知，在讨论a1, a2, Λ, ak的最小公倍数时，不妨假定它们都是正整数.在本节中总是维持这一假定.最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理.3、定理2对任意的正整数a，b，有[a, b] =ab(a,b).证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此ak1 = bk2.(1)于是abk1=k2.(a,b)(a,b)由于(ab,)= 1，所以(a,b)(a,b)b|k1，即k1=bt(a,b)(a,b)，其中t是某个整数.将上式代入式(1)得到m =abt.(a,b)(2)另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数.当t = 1时，得到最小公倍数[a, b] =ab(a,b).推论1两个整数的任何公倍数可以被它们的最小公倍数整除.证明由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2设m，a，b是正整数，则[ma, mb] = m[a, b].证明由定理2及前面的定理2的推论得到m2abm2abmab==[ma, mb] == m[a, b].(ma,mb)m(a,b)(a,b)证毕4、定理3对于任意的n个整数a1, a2, Λ, an，记[a1, a2] = m2，[m2, a3] = m3，Λ，[mn-2, an-1] = mn-1，[mn-1, an] = mn，则[a1, a2, Λ, an] = mn.证明：我们有mn = [mn-1, an] ⇒mn-1∣mn，an∣mn，mn-1 = [mn-2, an-1] ⇒mn-2∣mn-1∣mn，an∣mn，an-1∣mn-1∣mn，mn-2 = [mn-3, an-2] ⇒mn-3∣mn-2∣mn，an∣mn，an-1∣mn，an-2∣mn，ΛΛm2 = [a1, a2] ⇒ an∣mn，Λ，a2∣mn，a1∣mn，即mn是a1, a2, Λ, an的一个公倍数.另一方面，对于a1, a2, Λ, an的任何公倍数m，由定理2的推论及m2, Λ, mn的定义，得m2∣m，m3∣m，Λ，mn∣m.即mn是a1, a2, Λ, an最小的正的公倍数.证毕推论若m是整数a1, a2, Λ, an的公倍数，则[a1, a2, Λ, an]∣m.证明：留作习题.定理4整数a1, a2, Λ, an两两互素，即(ai, aj)= 1，1 ≤ i, j ≤ n，i ≠ j 的充要条件是[a1, a2, Λ, an] = a1a2Λan.(3)证明：必要性因为(a1, a2)= 1，由定理2得到[a1, a2] =a1a2(a1,a2)= a1a2.由(a1, a3)=(a2, a3)= 1及前面的定理4推论得到(a1a2, a3)= 1，由此及定理3得到[a1, a2, a3] = [[a1, a2], a3] = [a1a2, a3] = a1a2a3.如此继续下去，就得到式(3).充分性用归纳法证明.当n = 2时，式(3)成为[a1, a2] = a1a2.由定理2 a1a2 = [a1, a2] =即当n = 2时，充分性成立.假设充分性当n = k时成立，即[a1, a2, Λ, ak] = a1a2Λak ⇒(ai, aj)= 1，1 ≤ i, j ≤ k，i ≠ j.对于整数a1, a2, Λ, ak, ak + 1，使用定理3中的记号，由定理3可知[a1, a2, Λ, ak, ak + 1] = [mk, ak + 1].(4)其中mk = [a1, a2, Λ, ak].因此，如果[a1, a2, Λ, ak, ak + 1] = a1a2Λakak + 1，那么，由此及式(4)得到[a1, a2, Λ, ak, ak + 1] = [mk, ak + 1] =即mk(mk,ak+1)mkak+1(mk,ak+1)a1a2(a1,a2)⇒(a1, a2)= 1，= a1a2Λakak + 1，= a1a2Λak，显然mk ≤ a1a2Λak，(mk, ak + 1)≥1.所以若使上式成立，必是(mk, ak + 1)= 1，(5)并且mk = a1a2Λak.(6)由式(6)与式(5)推出(ai, ak + 1)= 1，1 ≤ i ≤ k；(7)由式(6)及归纳假设推出(ai, aj)= 1，1 ≤ i, j ≤ k，i ≠ j.(8)综合式(7)与式(8)，可知当n = k + 1时，充分性成立.由归纳法证明了充分性.证毕定理4有许多应用.例如，如果m1, m2, Λ, mk是两两互素的整数，那么，要证明m = m1m2Λmk整除某个整数Q，只需证明对于每个i，1 ≤ i ≤ k，都有mi∣Q.这一点在实际计算中是很有用的.对于函数f(x)，要验证命题“m∣f(n)，n∈Z”是否成立，可以用第二节例5中的方法，验证“m∣f(r)，r = 0, 1, Λ, m -1”是否成立.这需要做m次除法.但是，若分别验证“mi∣f(ri)，ri = 0, 1, Λ, mi - 1，1 ≤ i ≤k”是否成立，则总共需要做m1 + m2 +Λ+ mk次除法.后者的运算次数显然少于前者.例1设a，b，c是正整数，证明：[a, b, c](ab, bc, ca)= abc.解：由定理3和定理2有[a, b, c] = [[a, b], c] =由第三节定理5和定理2的推论，(ab, bc, ca)=(ab,(bc, ca))=(ab, c(a, b))=(ab,abc)=(ab[a,b],abc)=ab([a,b],c).[a,b][a,b][a,b][a,b]c，([a,b],c)(9)(10)联合式(9)与式(10)得到所需结论.例2对于任意的整数a1, a2, Λ, an及整数k，1 ≤ k ≤ n，证明：[a1, a2, Λ, an] = [[a1, Λ, ak],[ak + 1, Λ, an]].解：因为[a1, a2, Λ, an]是a1, Λ, ak, ak + 1, Λ, an的公倍数，所以由定理2推论，推出[a1, Λ, ak]∣[a1, a2, Λ, an]，[ak + 1, Λ, an]∣[a1, a2, Λ, an]，再由定理3推论知[[a1, Λ, ak], [ak + 1, Λ, an]]∣[a1, a2, Λ, an].另一方面，对于任意的ai（1 ≤ i ≤ n），显然ai∣[[a1, Λ, ak], [ak + 1, Λ, an]]，所以由定理3推论可知[a1, a2, Λ, an]∣[[a1, Λ, ak], [ak + 1, Λ, an]]，联合上式与式(11)得证.例3设a，b，c是正整数，证明：[a, b, c][ab, bc, ca] = [a, b][b, c][c, a].解：由定理2推论2及例2，有[a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca] = [[a2b, ab2, abc], [abc, b2c, bc2], [a2c, abc, ac2]] = [a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac2] = [abc, a2b, a2c, b2c, b2a, c2a, c2b] 以及(11)[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a] = [ab, b2, ac, bc][c, a] = [ab[c, a], b2[c, a], ac[c, a], bc[c, a]] = [abc, a2b, b2c, b2a, ac2, a2c, bc2, bca] = [abc, a2b, a2c, b2c, b2a, c2a, c2b]，由此得证.三、辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法.它是数论中的一个重要方法，在其他数学分支中也有广泛的应用.1、定义1下面的一组带余数除法，称为辗转相除法.设a和b是整数，b ≠0，依次做带余数除法：a = bq1 + r1，0 < r1 < |b|，b = r1q2 + r2，0 < r2 < r1，ΛΛrk - 1 = rkqk + 1 + rk + 1，0 < rk + 1 < rk，(1)ΛΛrn - 2 = rn - 1qn + rn，0 < rn < rn-1，rn - 1 = rnqn + 1.由于b是固定的，而且|b| > r1 > r2 > Λ，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理1用下面的方式定义Fibonacci数列{Fn}：F1 = F2 = 1，Fn = Fn - 1 + Fn - 2，n ≥ 3，那么对于任意的整数n ≥ 3，有Fn > α n - 2，(2)其中α =1+52.证明：容易验证α 2 = α+ 1.当n = 3时，由F3 = 2 >1+可知式(2)成立.假设式(2)对于所有的整数k ≤n（n ≥3）成立，即Fk > α k - 2，k ≤ n，则Fn + 1 = Fn + Fn - 1 > α n - 2 +α n - 3 = α n - 3(α+ 1)= α n - 3α 2 = α n- 1，即当k = n + 1时式(2)也成立.由归纳法知式(2)对一切n ≥ 3成立.证毕.3、定理1(Lame)设a, b∈N，a > b，使用在式(1)中的记号，则n < 5log10b.证明：在式(1)中，rn ≥ 1，qn + 1 ≥ 2，qi ≥ 1（1 ≤ i ≤ n），因此rn ≥ 1 = F2，rn - 1 ≥ 2rn ≥ 2 = F3，52= α rn - 2 ≥ rn - 1 + rn ≥ F3 + F2 = F4，ΛΛb ≥ r1 + r2 ≥ Fn + 1 + Fn = Fn + 2，由此及式(2)得b ≥αn =(1+即log10b ≥ nlog101+这就是定理结论.证毕4、定理2使用式(1)中的记号，记P0 = 1，P1 = q1，Pk = qkPk - 1 + Pk - 2，k ≥ 2，Q0 = 0，Q1 = 1，Qk = qkQk - 1 + Qk - 2，k ≥ 2，则aQk - bPk =(-1)k - 1rk，k = 1, 2, Λ, n.(3)证明：当k = 1时，式(3)成立.当k = 2时，有Q2 = q2Q1 + Q0 = q2，P2 = q2P1 + P0 = q2q1 + 1，此时由式(1)得到aQ2 - bP2 = aq2 - b(q2q1 + 1)=(a - bq1)q2 - b = r1q2 - b = -r2，即式(3)成立.假设对于k < m（1 ≤ m ≤ n）式(3)成立，由此假设及式(1)得到aQm - bPm= a(qmQm - 1 + Qm - 2)- b(qmPm - 1 + Pm - 2)52)n，52>1n，5=(aQm - 1 - bPm - 1)qm +(aQm - 2 - bPm - 2)=(-1)m - 2rm - 1qm +(-1)m - 3rm - 2 =(-1)m - 1(rm - 2 - rm - 1qm)=(-1)m- 1rm，即式(3)当k = m时也成立.定理由归纳法得证.证毕5、定理3使用式(1)中的记号，有rn =(a, b).证明：由第三节定理1，从式(1)可见rn =(rn - 1, rn)=(rn - 2, rn - 1)= Λ =(r1, r2)=(b, r1)=(a, b).证毕.现在我们已经知道，利用辗转相除法可以求出整数x，y，使得ax + by =(a, b).(4)为此所需要的除法次数是O(log10b).但是如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些.例1设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a, b).解：下面的四个基本事实给出了证明：(ⅰ)若a∣b，则(a, b)= a；(ⅱ)若a = 2αa1，2/|a1，b=2βb1，2/|b1，α≥β≥ 1，则(a, b)= 2β(2α-βa1, b1)；(ⅲ)若2/|a，b=2βb1，2/|b1，则(a, b)=(a, b1)；a-b(ⅳ)若2/|a，2/|b，则(a,b)=(||,b).2在实际计算过程中，若再灵活运用最大公约数的性质（例如第三节定理4的推论），则可使得求最大公约数的过程更为简单.例2用辗转相除法求(125, 17)，以及x，y，使得125x + 17y =(125, 17).解：做辗转相除法：= 7⋅17 + 6，q1 = 7，r1 = 6，= 2⋅6 + 5，q2 = 2，r2 = 5，6 = 1⋅5 + 1，q3 = 1，r3 = 1，5 = 5⋅1，q4 = 5.由定理4，(125, 17)= r3 = 1.利用定理2计算（n = 3）P0 = 1，P1 = 7，P2 = 2⋅7 + 1 = 15，P3 = 1⋅15 + 7 = 22，Q0 = 0，Q1 = 1，Q2 = 2⋅1 + 0 = 2，Q3 = 1⋅2 + 1 = 3，取x =(-1)3 -1Q3 = 3，y =(-1)3P3 = -22，则125⋅3 + 17⋅(-22)=(125, 17)= 1.例3求(12345, 678).解：(12345, 678)=(12345, 339)=(12006, 339)=(6003, 339)=(5664, 339)=(177, 339)=(177, 162)=(177, 81)=(96, 81)=(3, 81)= 3.例4在m个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n（n < m）个盒子中各放一个硬币.证明：若(m, n)= 1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币.解：由于(m, n)= 1，所以存在整数x，y，使得mx +ny = 1.因此对于任意的自然数k，有+m(-x + kn)= n(km + y)，这样，当k充分大时，总可找出正整数x0，y0，使得+mx0 = ny0.上式说明，如果放y0次（每次放n个），那么在使m个盒子中各放x0个后，还多出一个硬币.把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1.因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同.四、小结.五、作业24页ex5、ex6、ex7、ex8、ex11 25页ex16 26页ex29、ex36 第二篇：初等数论学习心得《初等数论》学习心得要写学习心得并不是什么难事，不过我觉得这一次的学习心得又有些不太一样的地方。