数论感想

第一篇：数论感想

本学期，我们分了专业方向，我选择的是信息安全，有幸听了数论基础课。根据这一学期的所学所想，我做了简单的总结。

其实，在分专业方向的时候，我对“信息安全”这个名词并没有什么概念，只是通过老师的介绍和查阅相关资料，才对这个方向有了浅显的认识。在信息膨胀、全球化网络化的今天，大量的数据信息在互联网上传播。因此，对于私密信息的保密处理显得尤为重要。

依然记得自己QQ号被盗时候的愤懑，虽然没有什么隐私可以泄漏，但是我对这种现象的出现就感到很不愉快。加上互联网正值壮年，蓬勃发展的时期，黑客的疯狂出现与信息的泄露成为互联网维护的一大难题。因此，我非常想拥有保护自己隐私的能力。同时，我个人一直对网络攻防方面很有兴趣，对这个新生起的环境有着极大的好奇心。因此，我毅然选择了信息安全这条道路。

通过老师的讲授、相关资料的查询以及与同学的讨论，我了解到信息安全的基础是加密处理，掌握了最基本的加密原理，才能对破密及防盗有进一步的研究。所以，这就需要密码学这门课来完善我们的基础知识体系。同时，记得老师说过信息安全的尖端拼的是数学功底，我们需要的是强大的数学思维以及深厚的数学功底。所以，我们学院安排了密码学基础和抽象代数这两大专业课。这两门课将对我们今后的学习工作提供最基础的理论与逻辑的支持，但是，同时又要求有更加基础的学科来做铺垫，那就是我们这堂课所学的数论基础。由于种种原因，我们这届的数论基础课是第一届开课，也将是最后一节课，我不免对未来失去学习这门课的学弟学妹们表示遗憾。

我对“数论”这个名词的概念来自于高中数学竞赛期间参加的培训班，当时有许多名师来为我们讲授各种竞赛知识，包括苏远东教授和陶平生教授的初等数论。因此，当我听说我们要学习这门课的时候，我很是高兴，感觉毫无压力。但是，当我翻开《数论讲义》这本教材的时候，顿时心中一凉。正如前言所述，初等数论是主要用算术方法研究整数性质的一个数论分支，它是数学中最古老的分支之一。同时，在数学发展史上，常常可以发现，对初等数论中某些问题的研究，曾促使数学中新分支的发展。近几十年来，初等数论在计算机科学、组合数学、代数编码、信号的数字处理等领域内得到广泛的应用，而且许多较深刻的结果都得到了应用。其实大学的数论基础知识数论领域中的一角，而我们高中所接触的数论知识只占了本教材的第一章内容，是皮毛中的皮毛。所以，我顿时感觉任重而道远啊。详细翻阅本教材里面的内容，涉及范围很广，从整数性质引出同余关系，进而延伸到二次剩余及原根次数的求解，并在最后逐步涉及到素性的判别。这么多的内容包含在区区180页的书中，可想“教材内部的空虚”。但是，郭老师讲课的风格很适合我们这些初学者，教材、ppt和板书的结合，不仅将整个书的内容做了充分的扩充，还教会了我们解决数学问题的基本思想。这种处理问题的思想是在课上潜移默化习得的，也是成为一名网络高手不可或缺的财富。虽然这门课程结束了，但是老师教给我们的这些思想是永恒的。结合本学期所学的抽象代数，可以看出，数论是抽象代数的具体体现，而抽象代数则是数论的抽象化、代数化、逻辑化、理论化延伸，两者相生相和，结合成了我们这学期所收获的对信息安全课程最基本的认识。

最后，感谢老师这学期教给我们的一切知识、解题方法以及数学思想。我现在对信息安全这个分支的了解还只是停留在表面，以后的学习工作中还会向您请教，并在自己选择的方向上作出一番成绩。

第二篇：初等数论复习题

1、如果(a,b)1，则(ab,ab)=

2、求[136,221,391]=

3、{-9/7}=；

4、当x不是整数时，{-x}=；

5、模11的最小正完全剩余系是 {} ；

6、设2a与3b是正整数，则在1, 2, …,2 a中能被3b整除的整数有7、154440的标准分解式是；

8、今天是星期一，过10100天后是；

9、2000！中末尾0的个数有。

10、求15！的标准分解式。

11、解不定方程6x17y18.12、求不定方程25x13y7z4的所有正整数解。

13、将17/105 写成三个既约分数之和，它们的分母分别是3，5和7。

14、用数学归纳法证明：证明相邻两个偶数的乘积是8的倍数.15、证明：素数的个数无穷多。

16、证明：如果a,b是两个整数,b0,则存在唯一的整数对q,r,使得abqr,其中0rb.17、第一章课后练习选两题。；

第三篇：初等数论学习心得

《初等数论》学习心得

要写学习心得并不是什么难事，不过我觉得这一次的学习心得又有些不太一样的地方。在选课的时候，我并不盲目跟随，不仅仅是为了拿学分，我有自己的想法。因为，作为一个即将走向教师讲台的师范类数学专业的毕业生，如果连一些比较基本的东西都不了解，那怎么能够在学生面前讲解呢。基于此，我选择了《初等数论》这门课程，并希望能在此收获一些东西。

虽然之前就了解过一些关于数论的知识，但仅仅是皮毛上的了解，再说也不能系统地接触到这门课程。不过，通过这几节课的学习，我对初等数论》这门课程有了进一步的了解和认识。通过一个多星期的学习，我了解到这门课程主要研究的一些内容。

一、整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。

二、同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果： 二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。

三、连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果： 循环连分数展开、最佳逼近问题、佩尔方程求解。

四、不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了4次费马方程的求解问题等等。

五、数论函数。比如欧拉函数、莫比乌斯变换等等。

六、高斯函数。在数学领域，高斯函数在厄尔米特多项式的定义中起着重要作用。

我知道一个星期的时间是不可能把《初等数论》这门课程学得很好的，只能大致的了解它的全貌或者说是对某一部分的内容进行研究。在这些天的学习中，我对数学这个浩瀚海洋里的《初等数论》部分的内容有了更进一步的认识，这为我以后走上教学岗位，提升专业素养有着不可分割的关系，也许就是这么一些点点滴滴的学习和积累才能让一个数学教师在自己的三尺讲台上站得更稳，才能成为学生眼中知识渊博的老师。

总之，这一个多星期的学习让我受益匪浅，让我在专业知识上又迈进了一步，虽然不能深入研究，但在面上的了解更广了，至少能够收获一些之前我所想要的，开拓和丰富了我对数学世界的视野。尤其是老师主要讲解的整除理论和同余理论与我以后走上讲台后所需要用到的知识联系非常密切，它会在我的教师成长之路上一直伴我前行！

第四篇：ZJZ数论练习(一)

ZJZ数论练习

（一）1.设Mp=2p-1，p是素数，证明：若p≠q，则 Mp，Mq =1.2.设p是素数，且p²+71的不同正因数的个数不超过10个，求p.3.已知m，n，k是正整数，且mn|nm，nk|kn，证明：mk|km.4.已知a是正整数，且a4+a3+a2+a+1是完全平方数，求所有满足条件的a

5.设n为正整数.证明：22+22nn−1+1至少有n个不同的素因子.6.证明：若正整数a、b满足2a²+a=3b²+b，则a-b是完全平方数.7.证明：有无穷多个奇数m，使8m+9m²是合数.8.设m，n，k都是正整数，满足[m+k，m]=[n+k，n]，证明：m=n.9.设正整数a，b，c，d满足ab=cd，证明：a+b+c+d不是素数.10.设整数a、b、c、d满足a>b>c>d>0，且a²+ac-c²=b²+bd-d².证明：ab+cd不是

素数.

第五篇：初等数论教案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，  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