初等数论闵嗣鹤版课件

1、第一章 整数的可除性一 初等数论及其主要内容 数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即质数）分布 以及数论函数等内容，统称初等数论 （elementary number theory） 。 初等数论是数论中不求助于其他数学学科的帮助，只依靠初等的方法来研究整数性质的分支。 自古以来，数学家对于整数性质的研究一直十分重视，初等数论的大部份内容早在古希腊欧几里德的几何原本（公元前3世纪）中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。我国古代在数论方面亦有杰出之

2、贡献，现在一般数论书中的“中国剩余定理”，正是我国古代孙子算经中的下卷第26题，我国称之为孙子定理。 近代初等数论的发展得益於费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，德国数学家高斯集中前人的大成，写了一本书叫做算术探究，开始了现代数论的新纪元。高斯还提出：“数学是科学之王，数论是数学之王”。二 数论的发展 由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算机科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用，无疑同时也促进着数论的发展。 我

3、国近代：在解析数论、丢番图方程，一致分布等方面有过重要贡献，出现了华罗庚、闵嗣鹤等一流的数论专家，其中华罗庚在三角和估值、堆砌素数论方面的研究享有盛名。 特别是在“篩法”、歌德巴赫猜想方面的研究，已取得世界领先的优异成绩。陈景潤在1966年证明歌德巴赫猜想方面证明了”1+2”(一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和)三、几个著名数论难题 初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。 其中，非常著名的问题有：哥德巴赫猜想 ；费尔马大定理 ；孪生素数问题 ；完全数问题等。 1742年,由德

4、国中学教师哥德巴赫在教学中首先发现的。1742年6月7日，哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想： 一个大于6的偶数可以表示为不同的两个质数之和。 陈景润在1966年证明了“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”所谓的1+2，是筛法的光辉顶点，至今仍是“哥德巴赫猜想”的最好结果。 1、哥德巴赫猜想：2、费尔马大定理： 费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，世人冠以“业余王子”之美称。在三百七十多年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处

5、，写下一个看起来很简单的定理。 经过8年的努力，英国数学家 安德鲁怀尔斯 终于在1995年完成了该定理的证明。)3( nzyxnnn方程 无非0整数解3、孪生素数问题 存在无穷多个素数 p, 使得 p+2 也是素数。 究竟谁最早明确提出这一猜想已无法考证，但是1849年法国数学家 Alphonse de Polignac 提出猜想： 对 于任何偶数 2k, 存在无穷多组以2k为间隔的素数。对于 k=1，这就是孪生素数猜想，因此人们有时把 Alphonse de Polignac 作为孪生素数猜想的提出者。不同的 k 对应的素数对的命名也很有趣，k=1 我们已经知道叫做孪生素数； k=2 (即间

6、隔为4) 的素数对被称为 cousin prime ；而 k=3 (即间隔为 6) 的素数对竟然被称为 sexy prime (不过别想歪了，之所以称为 sexy prime 其实是因为 sex 正好是拉丁文中的 6。) 4、最完美的数完全数问题 下一个具有同样性质的数是28, 28=1+2+4+7+14.接着是496和8128.他们称这类数为完美数. 欧几里德在大约公元前350-300年间证明了: 注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数。 完美数又称为完全数,最初是由毕达哥拉斯的信徒发现的,他们注意到,数6有一个特性,它等于它自己的因子(不包括它自身)的和， 如：6=

7、1+2+3.若 是素数，则 是完全数 12 n) 12(21nn 在培养中学生思维能力方面大有作用。四、初等数论在中小学教育中的作用国际数学奥林匹克从1959年起到2002年已经举行了43届比赛，大致统计，在总共260道题目中，可以主要用初等数论知识来解及初等数论知识有关的约有82题，约占31.5%。第一节 整除的概念 带余数除法qabqabb a如果不存在整数 使得成立，则称 不被 整除，记为。2、整除的基本定理、整除的基本定理思考：逆命题是否成立？1、m|(ab) m|a,m|b2、m|(ab) ，m|am|bbmbamam|)( |,|定理2特例：m|a m|aq3 3、带余数除法、带余

8、数除法4,00a bbqrabqrrbqr带余数除法的第二种表示定理若是两个整数，其中，则存在着两个整数及 ，使得，成立，而且 及 是唯一的。,00,qZaq brab qrbbqq r证明分析：作整数序列，-3 b ,-2 b ,- b ,0,b ,2 b ,3 b ,则a必满足q ba(q+1)b ,其中令可得到分和来讨论进一步证明的唯一性。4,02a bbbqrabqrrqrqr带余数除法的第三种表示（课后习题）定理若是两个整数，其中，则存在着两个整数及 ，使得，成立，而且当b是奇数时， 及 是唯一的；当b是偶数时， 及有可能是不唯一的。5,252313,1;52212,1abqrqr

9、例当时，可有（） （） （），即或（） （） ，即222222,220000,qZbbbbqrq r证明分析：作序列3 b2 bbb 2 b 3 b，-,-,-,0,bb则a必满足qa(q+1),其中分q为偶数时和；q为偶数时和来讨论 及 的存在性 进一步证明的唯一性。例例1 求当b=15时, a取下列数值时的不完全商和余数.1、a=81; 2、a=-81; 例例2(1)一个数除以2,余数可能为 ,所有的整数按被2除所得的余数分类可分为 . (2)一个数除以3,余数可能为 ,所有的整数按被3除所得的余数分类可分为 . ( 3 ) 一 个 数 除 以 正 整 数 b , 余 数 可 能为 ,所有

10、的整数按被b除所得的余数分类可分为 . 带余数除法的应用举例带余数除法的应用举例例例1 1 证明形如证明形如3n-13n-1的数不是平方数。的数不是平方数。2,3,03(3)31,03.aZaqrrqrnr 证明：，而例例 2 2 、 任 意 给 出 的、 任 意 给 出 的 5 5 个 整 数 中 ， 必 有个 整 数 中 ， 必 有 3 3 个 数 之个 数 之和被和被3 3整除。整除。5,1,5303,1,5iiiiia iaqrri证：设这 个数为，记，。分别考虑以下两种情形,0120,1,23()33irrrrraaaqqq( 若在中数 ， ，都出现，不妨设

11、， 此时可以被 整除 ),0120,123()33iiirrrrrrr raaaqqqr若在中数 ， ，至少有一个不出现，这样至少有3个 要取相同的值，不妨设(或 ）， 此时可以被 整除。311,21dadaa例 、设为奇数，证明：存在正整数使得0112 ,2 ,22 (0)ajaaja证：考虑下面的 个数：，显然 不整除，2 (0)2,(0)jjjjjjaq arra由带余除法，对每个，011, ,1aar rra因而 个余数仅可能取个值，因此其中必有两个相等。0()222 (21)ikkiik ikirrikaa qq 设为 ， ，不妨设，因而有211k iadk

12、iad 则有，取，则 就满足要求。0()222 (21)ikkiik ikirrikaa qq 设为 ， ，不妨设，因而有011, ,1aar rra因而 个余数仅可能取个值，因此其中必有两个相等。例4例6第二节第二节 最大公因数与辗转相除法最大公因数与辗转相除法1212121212,(2),=1,nnnnna aan nda aaa aaa aaa aa1、定义设是个整数，若整数 是它们之中每一个的因数，那么d就叫作的一个公因数。所有公因数中最大的一个叫最大公因数，记作（），若（） ，则说互质或互素。2 2、任意整数的最大公因数可转化为正整数来讨论、任意整数的最大公因数可转化为正整数来讨论3

13、 3、下面先讨论两个非负整数的最大公因数、下面先讨论两个非负整数的最大公因数定理定理2 2、设、设b b是任一正整数，则（是任一正整数，则（i)0i)0与与b b的公因数就是的公因数就是b b的因数，反之，的因数，反之， b b的因数也就是的因数也就是0 0与与b b的公因数。的公因数。(ii)(0,b)=b(ii)(0,b)=b2.1(0, )bbb推论若 是任一非零整数，则4 4、定理、定理3 3 设设a,b,ca,b,c是三个不全为零的整数，且是三个不全为零的整数，且a=bq+ca=bq+c其中q是非零整数，则a,b与b,c有相同的公因数，因而(a,b)=(b,c)思考：1、d|a,d|

14、c时能否推出d|b? 5、下面要介绍一个计算最大公约数的算法下面要介绍一个计算最大公约数的算法辗转辗转相除法，又称相除法，又称EuclidEuclid算法。它是数论中的一个重要算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。方法，在其他数学分支中也有广泛的应用。定义定义 下面的一组带余数除法，称为辗转相除法。下面的一组带余数除法，称为辗转相除法。12221 0 brqrrr，111 0 babqrr，1 1 1 1 0 kkkkkkrr qrrr，,0a bb 设是整数，依次做带余数除法211 0 nnnnnnrrqrrr，1 111+0nnnnnrr qrr,。4,( , )

15、nna ba brr定理若是任意两个正整数，则，是上式中最后一个不等于零的余数。4.1,( , )a ba b推论的公因数与的因数相同。1859,1573,( 1859,1573)ab例1、求6 6、最大公因数的两个性质、最大公因数的两个性质5, ,( )(,)( , ),( ),1( , ) ( , )a bi mam bma b ma babiia baba ba b定理设是任意两个不全为零的整数，是任一正整数，则 若 是的任一公因数，则，特别 对于两个以上整数的最大公因数问题，不妨设121222331,(,),(,),(,).nnnna aana addaddad是任意 个正整数，令于是

16、我们有2142143nnn例 、证明：若 是正整数，则是既约分数。214,143)(71,143)nnnn证明：因为（(71,72)(71,1)1nnn所以，命题得证。第三节 整除的进一步性质及最小公倍数0000( , ),ka baxbyxya bra b第二节习题第二题要求证明成立，其中的 和 与的关系如何？进一步，辗转相除法中任意 与的关系又如何？2.1,( , )a bstasbta b推论若是任意两个不全为零的整数，则存在两个整数 ， 使得22172 65,2,5qr 3361 5 1,1,1qr 3(125,17)1r由定理得例例 用辗转相除法求(125, 17)，以及x，y，使得

17、 125x 17y = (125, 17)。解 做辗转相除法：111257 176,7,6qr01231,7,2 7 1 15,1 15722,PPPP 01230,1,2 102,1 2 13,QQQQ 3 1333( 1)3,( 1)22,xQyP 取125 3+1722 （-）=(125,17)=1则2, ,( , )1,)(, )( , ),a b ca cab cb ciiab cb cb c定理 、若是三个整数，且，则（i)与有相同的公因数，（上面假定了至少有一不为零。2.1( , )1,.a cc abc b推论、若，则1212121 22.2,)1nmnma aab bba a

18、a bbb推论、设及 ,是任意两组整数，若前一组中任一整数与后一组中任一整数互质，则(121212,(2), ,nnna aan ndna aaa aa定义设是个整数，若整数 是这 个数的倍数，则d就叫作的一个公倍数。所有公倍数中最小的一个叫最小公倍数，记作。12123,.nna aaaaa定理, ( ) ,.,( , )a ba ba bii a baba ba ba baba b定理4设是任意两个正整数，则(i)的所有公倍数就是的所有倍数；的最小公倍数等于以它们的最大公因数除它们的乘积所得的商，即=特别地，当（）=1，则= 对于两个以上整数的最小公倍数问题，不妨设121222331,.nn

19、nna aana ammammam是任意 个正整数，令于是我们有1212,.nnna aana aam定理5是 个正整数，则 注：多项式的带余除法类似于整数的带余除法第四节 质（素）数 算术基本定理一、质（素）数一、质（素）数1、定义 一个大于1的整数，如果它的正因数只有1及它本身，就叫做质数（或素数）；否则就叫合数。2、与素数相关的性质定理111aaqaqa定理设 是任一大于 的整数，则 的除 外最小正因数 是一素数，并且当 是合数时，2=1paappaapp定理设 是一素数， 是任一整数，则 能被 整除或 与 互质，即（ ， ） 或 。1212.,.nnka aanpp a aapa推论2

20、1设是 个整数， 是素数.若，则 一定能整除某一1.aaaa定理若是整数，则 是素数不大于的素数都不能整除.aa充分性：设不大于的素数都不能整除1app若 是合数，设 是除 外的最小正因数，则 是素数。211apaapappa令,则，即，这样就找到一个证：必要性显然。apaa不大于的素数 ，它可以整除 ，矛盾， 是素数。 对于一个给定的整数，我们根据上述定理不仅可以判别它是否是素数，且还可以找出所有不大于它的素数,1,2,3,4,5,6,7,aZa aa的素数倍数划去后，剩下的数就是所有不大于把1划去，剩下第一个数是2,2是素数。从2起划去它后面所有2的倍数，剩下的第一个数是3，它不是2的倍所

21、以它是素数。 依次，当我们把所有的不大于的素数。 这种方法是希腊时代幼拉脱斯展纳发明的，好像用筛子筛出素数一样，称幼拉脱斯展纳筛法。数的素性检验方法问题在近几年得到了飞速的发展, 若用计算机编成程序,对于10位数,几乎瞬间即可完成, 对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到1036年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的过去,要检验一个数是否是素数，最简单方法是试除法， 检验一个20位数只消10

22、秒钟,对于一个50位数用15秒钟, 100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.技巧,现在以他们的名字的首字母命名的ARCL检验法 定理3、素数的个数是无穷的。注：2000多年前，古希腊数学家欧几里得（前330-前275），著有几何原本，他在此书中率先证明了素数的无限性，这个证明一直被当作数学证明的典范，受到历代数学家的推崇，因为这一定理及其证明既简洁、优美而不失深刻。其证明思路如下：证明: 假设正整数中只有有限个质数，设为1212,.11.kkp ppp ppNN 令，则1,1,2, .iNp

23、pp ik由定理 ， 有一素因数 ，这里12,1kp p ppp Npp否则，因此，而与 是素数矛盾。故.pk是上面 个素数以外的素数，因此定理获证下面介绍与素数有关的某些问题1、费马数：费马在1640年设计了一个公式，给出一些素数。221nnnF 费马坚信对于所有自然数 ，总能产生素数。52521641 6700417F 然而他大错特错了！只有五个素数被发现是遵从于这个公式的，它们是3,5,17,257和65537,分别对应于n=0,1,2,3,42、费马数与尺规作图的联系：尺规作图是指用没有刻度的直尺和圆规作图。尺规作图 瑞士科学家欧拉于1732年举出故费马的猜测不正确。规作图使用的直尺和

24、圆规带有想像性质，跟现实中的并非完全相同：1、直尺必须没有刻度，无限长，且只能使用直尺的固定一侧。只可以用它来将两个点连在一起， 不可以在上画刻度； 2、圆规可以开至无限宽，但上面亦不能有刻度。它只可以拉开成之前构造过的长度。 只准许使用有限次，来解决不同的平面几何作图题。尺是起源于古希腊的数学课题。只使用圆规和直尺，并且221n1796年，19岁的高斯证明了：对于边数是素数的正多边形，当边数是形如的费马数时，才能用尺规作图，并且给出正17边形的尺规作图法。2knn正 边形能尺规作图为与不同费马素数积的乘积。一般地，任意正n边形有以下结论：3、梅森数梅森数(Mersenne number)是指

25、形如2p1的正整数， 其中指数p是素数，常记为Mp 。若Mp是素数，则称为梅森素数。早在公元前300多年，古希腊数学家欧几里得就开创了研究2P1的先河，他在名著几何原本 第九章中论述完美数时指出：如果2P1是素数， 则(2p1)2(p1)是完美数。 梅森在欧几里得、费马等人的有关研究的基础上 ，对2P1作了大量的计算、验证工作，并于1644年在他的 物理数学随感一书中断言：对于p=2，3，5，7，13，17，19，31，67，127，257时，2P1是素数 而对于其他所有小于257的数时，2P1是合数。 前面的7个数属于被证实的部分，是他整理前人的工作得到的；而后面的4个数属于被猜测的部分。

26、值得提出的是：虽然梅森的断言中包含着若干错误， 但他的工作极大地激发了人们研究2P1型素数的热情， 在梅森素数的基础研究方面，法国数学家鲁卡斯和美国 数学家雷默都做出了重要贡献；以他们命名的“鲁卡斯-雷默方法”是目前已知的检测梅森素数素性的最佳方法。 此外，中国数学家和语言学家周海中给出了梅森素数分布的精确表达式，为人们寻找梅森素数提供了方便；这一研究成果被国际上命名为“周氏猜测”。2005年，美国数学家C.Cooper和S.Boone领导的科研小组发现了第43个梅森素数，该素数有9 152 052位数，是目前知道的最大的素数， 该素数是：30 402 457211121(1)21204723

27、 89.nnn 若是素数，则 是素数.其逆命题不成立，例如关于梅森数有下列的一个命题：二、算术基本定理1、定理4 任一大于1的整数能表成素数的乘积，即任一大于1的整数121212121212,(1),1,2,nnnmmmiiap ppppppppaq qqqqqqqqmnqp in其中 ， ，是素数，并且若，其中 ， ， ，是素数，则，。此为算术基本定理。2、正整数的标准分解式推论4.1 任一大于1的整数a能够唯一地写成1212,0,1,2, ,()kkiijap ppikpp ij其中12121212,0,1,2, ,0,1,2,kkkikiiap ppikaddp ppikdda则 的正因

28、数 可以表成的形式，而且当 可以表成上述形式时， 是 的正因数。推论4.2 设a是任一大于1的整数，且推论4.3 设a,b是任意两个正整数，且12121212,0,1,2, ,0,1,2, ,kkkikiap ppikbp ppik12121212( , ), , ,min(,),max(,)1,2, .kkkkiiiiiia bp ppa bp ppik 则其中， , ( , )aba ba b注：利用推论容易证明：定理5 设a是任一大于1的正整数1212,0,1,2,kkiap ppikaa是 的标准分解式，则 的正因数个数为121( )(1)(1)(1)(1)kkiiT a 111110

29、011( )1ikkkkikiiapS appp的所有正因数的和为1( )2( )T aaP aa的所有正因数的乘积为121212124.2,0,1,2, ,0,1,2,kkkikiiap ppikaddp ppik证明：由推论，的正因数 可以唯一地表成，1,2,1,2,1iiiiiiikaikad(1)于是可以通过依次确定 （）作出 的正因数.因为 （）可以是0，1，2， ，这个数中的任意一个，即确定 的方法有种，所以 的不同正因数 的个数为：121( )(1)(1)(1)(1)kkiiT a 1212,001,2,(2)( )kiikd a dikaS adp pp的所有正因数的和为121

30、12211000kkkkppp1211111211211111111kikkiikipppppppp12( )12( ),1,2, ( ),T aiiT ad ddaad diT addda(3)若是 的所有正因数，令，则也是 的所有正因数，1122( )( )1( )( )2T aT aT aT ad dd dddaa（）（） （）12( )12( )( ),T aT aaP ad ddd dd故 的所有正因数的乘积为第五节第五节 函数函数x,x及其在数论中的一个应用及其在数论中的一个应用一、取整函数及性质1、取整函数x的定义:函数x与x是对于一切实数都有定义的函数，函数x的值等于不大于x的

31、最大整数； 函数x的值是x-x.把x叫做x的整数部分，x叫做x的小数部分。23 3,4,0,1;3532, 0.14159, 20.414,551 0.141590.95840 例如：问题：这两个函数的图像如何？2、取整函数的简单性质(1) xxx(2) 1,1 ,0 1xxxxxxx (3) ,nxnxn是整数(4) , + xyxyxyxy , + , xxxyyyxyxyxy证：0 + 2, + 01xyxy或 + + 1x yxyxyxyxy或 + x yxy( ) + xyx y 由此可得 + ()( )() + xyxyxyxyx yxy从而 1 xxZxxxZ(5) xZxxx

32、证：当时，； 1,- 0, 1xZxxx 当时，0-1( ) 1xxxxxx 1(9),mnn mZnn01mqnrrn证1,mrmrnqnnnnn(6)-1xx 小于 的最大整数是xx （7）不小于 的最小整数是 1xx （8）大于 的最小整数是(10),001a bZ baaaabbbbbbb 带余数除法：，则，aaaaaabbbbbbb 证明：，(11),a bZabab 则不大于 而为 的倍数的正整数的个数是110,0ambmamb 例题11 2 2xRxxx 例 、证明：，有 ,111 2 222xxxxxxxxxx证：2 2 2 2 2 xxxxx；1 2 2xx则原命题等价于证1

33、110 , 1,02 122212 02xxxxx当时，故111 1,1 1 ,12 222212 12xxxxx当时，故2121 nnnnnn例 、设 是任一正整数， 是实数，证明：121( ) nfnnnn证明：令111+11nfnnnn则注：此为厄米特恒等式。 11 11nnnn 11( )nnfnn1,( )R ffn即对11,( )0,ffnn又因为当0时2,( )0fn所以当0时，,( )0 xR f 因此，厄米特恒等式成立。121212123( )()( )0( )( )xn xxxyf x xxxixxxyf xMf nn 例 、平面上坐标为整数的点称为整点或格点，设是实数，是

34、非负连续函数，证明：区域：，上的整点的个数，这里 取整数值；1212,1( ),1( )1( )( )( )xn xxnyf nnxnxxnyf nyf nyf nMf n 证：区域上的整点都是在这样的直线段上：， 是一满足的整数，而直线段上的整点数就是满足条件的整数 的个数，有个，则1212( ) ( )0 xn xii xxMf n 12121212121212121221 121= ( )( )( )( )( )0( )11 ( )0 xn xxn xxn xxn xxn xxn xxn xxnxxn xMf nf nf nMf nf nf nxxxxMf n 证：0022)1122qpxyiiipqpqpqxyqp