初等数论闵嗣鹤版

第一章整数的可除性一初等数论及其主要内容数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即质数）分布以及数论函数等内容，统称初等数论（elementarynumbertheory）。初等数论是数论中不求助于其他数学学科的帮助，只依靠初等的方法来研究整数性质的分支。自古以来，数学家对于整数性质的研究一直十分重视，初等数论的大部份内容早在古希腊欧几里德的《几何原本》（公元前3世纪）中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”，正是我国古代《孙子算经》中的下卷第26题，我国称之为孙子定理。近代初等数论的发展得益於费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，德国数学家高斯集中前人的大成，写了一本书叫做《算术探究》，开始了现代数论的新纪元。高斯还提出：“数学是科学之王，数论是数学之王”。二数论的发展由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算机科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时也促进着数论的发展。•我国近代：在解析数论、丢番图方程，一致分布等方面有过重要贡献，出现了华罗庚、闵嗣鹤等一流的数论专家，其中华罗庚在三角和估值、堆砌素数论方面的研究享有盛名。•特别是在“篩法”、歌德巴赫猜想方面的研究，已取得世界领先的优异成绩。陈景潤在1966年证明歌德巴赫猜想方面证明了”1+2”(一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和)三、几个著名数论难题初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。其中，非常著名的问题有：哥德巴赫猜想；费尔马大定理；孪生素数问题；完全数问题等。1742年,由德国中学教师哥德巴赫在教学中首先发现的。1742年6月7日，哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想：一个大于6的偶数可以表示为不同的两个质数之和。陈景润在1966年证明了“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”〔所谓的1+2〕，是筛法的光辉顶点，至今仍是“哥德巴赫猜想”的最好结果。1、哥德巴赫猜想：2、费尔马大定理：费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，世人冠以“业余王子”之美称。在三百七十多年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处，写下一个看起来很简单的定理。经过8年的努力，英国数学家安德鲁·怀尔斯终于在1995年完成了该定理的证明。)3(nzyxnnn方程无非0整数解3、孪生素数问题存在无穷多个素数p,使得p+2也是素数。究竟谁最早明确提出这一猜想已无法考证，但是1849年法国数学家AlphonsedePolignac提出猜想：对于任何偶数2k,存在无穷多组以2k为间隔的素数。对于k=1，这就是孪生素数猜想，因此人们有时把AlphonsedePolignac作为孪生素数猜想的提出者。不同的k对应的素数对的命名也很有趣，k=1我们已经知道叫做孪生素数；k=2(即间隔为4)的素数对被称为cousinprime；而k=3(即间隔为6)的素数对竟然被称为sexyprime(不过别想歪了，之所以称为sexyprime其实是因为sex正好是拉丁文中的6。)4、最完美的数——完全数问题下一个具有同样性质的数是28,28=1+2+4+7+14.接着是496和8128.他们称这类数为完美数.欧几里德在大约公元前350-300年间证明了:注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数。完美数又称为完全数,最初是由毕达哥拉斯的信徒发现的,他们注意到,数6有一个特性,它等于它自己的因子(不包括它自身)的和，如：6=1+2+3.若是素数，则是完全数12n)12(21nn•在培养中学生思维能力方面大有作用。四、初等数论在中小学教育中的作用国际数学奥林匹克从1959年起到2002年已经举行了43届比赛，大致统计，在总共260道题目中，可以主要用初等数论知识来解及初等数论知识有关的约有82题，约占31.5%。第一节整除的概念带余数除法†qabqabba如果不存在整数使得成立，则称不被整除，记为。2、整除的基本定理思考：逆命题是否成立？1、m|(a±b)→m|a,m|b2、m|(a±b)，m|a→m|bbmbamam|)(|,|定理2’特例：m||am|aq3、带余数除法4,00abbqrabqrrbqr带余数除法的第二种表示定理若是两个整数，其中，则存在着两个整数及，使得，成立，而且及是唯一的。,,00,,qZaqbrabqrbbqqr证明分析：作整数序列，-3b,-2b,-b,0,b,2b,3b,则a必满足qba(q+1)b,其中令可得到分和来讨论进一步证明的唯一性。4,02abbbqrabqrrqrqr带余数除法的第三种表示（课后习题）定理若是两个整数，其中，则存在着两个整数及，使得，成立，而且当b是奇数时，及是唯一的；当b是偶数时，及有可能是不唯一的。5,252313,1;52212,1abqrqr例当时，可有（）（）（），即或（）（），即222222,220000,,qZbbbbqrqr证明分析：作序列3b2bbb2b3b，-,-,-,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,余数可能为,所有的整数按被b除所得的余数分类可分为.带余数除法的应用举例例1证明形如3n-1的数不是平方数。2,3,03(3)31,03.aZaqrrqrnr证明：，而例2、任意给出的5个整数中，必有3个数之和被3整除。5,1,,5303,1,,5iiiiiaiaqrri证：设这个数为，记，。分别考虑以下两种情形：15123123123),,0120,1,23()33irrrrraaaqqq(若在中数，，都出现，不妨设，此时可以被整除。15123123123(),,0120,123()33iiirrrrrrrraaaqqqr若在中数，，至少有一个不出现，这样至少有3个要取相同的值，不妨设(或），此时可以被整除。311,21dadaa例、设为奇数，证明：存在正整数使得0112,2,,22(0)ajaaja证：考虑下面的个数：，显然不整除，2(0)2,(0)jjjjjjaqarra由带余除法，对每个，011,,,1aarrra因而个余数仅可能取个值，因此其中必有两个相等。0()222(21)ikkiikikirrikaaqq设为，，不妨设，因而有211kiadkiad则有，取，则就满足要求。0()222(21)ikkiikikirrikaaqq设为，，不妨设，因而有011,,,1aarrra因而个余数仅可能取个值，因此其中必有两个相等。例4例6第二节最大公因数与辗转相除法1212121212,,,(2),,,,,,,,,=1,,,nnnnnaaanndaaaaaaaaaaaa1、定义设是个整数，若整数是它们之中每一个的因数，那么d就叫作的一个公因数。所有公因数中最大的一个叫最大公因数，记作（），若（），则说互质或互素。2、任意整数的最大公因数可转化为正整数来讨论3、下面先讨论两个非负整数的最大公因数定理2、设b是任一正整数，则（i)0与b的公因数就是b的因数，反之，b的因数也就是0与b的公因数。(ii)(0,b)=b2.1(0,)bbb推论若是任一非零整数，则4、定理3设a,b,c是三个不全为零的整数，且a=bq+c其中q是非零整数，则a,b与b,c有相同的公因数，因而(a,b)=(b,c)思考：1、d|a,d|c时能否推出d|b?5、下面要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义下面的一组带余数除法，称为辗转相除法。12221    0brqrrr，，111    0babqrr，，1111 0kkkkkkrrqrrr，，,0abb设是整数，，依次做带余数除法211 0nnnnnnrrqrrr，，1111+0nnnnnrrqrr,。4,(,)nnababrr定理若是任意两个正整数，则，是上式中最后一个不等于零的余数。4.1,(,)abab推论的公因数与的因数相同。1859,1573,(1859,1573)ab例1、求6、最大公因数的两个性质5,,()(,)(,),(),,,1(,)(,)abimambmabmababiiabababab定理设是任意两个不全为零的整数，是任一正整数，则若是的任一公因数，则，特别对于两个以上整数的最大公因数问题，不妨设121222331,,,(,),(,),,(,).nnnnaaanaaddaddad是任意个正整数，令于是我们有2142143nnn例、证明：若是正整数，则是既约分数。214,143)(71,143)nnnn证明：因为（(71,72)(71,1)1nnn所以，命题得证。第三节整除的进一步性质及最小公倍数0000(,),,kabaxbyxyabrab第二节习题第二题要求证明成立，其中的和与的关系如何？进一步，辗转相除法中任意与的关系又如何？2.1,(,)abstasbtab推论若是任意两个不全为零的整数，则存在两个整数，使得2217265,2,5qr336151,1,1qr3(125,17)1r由定理得例用辗转相除法求(125,17)，以及x，y，使得125x17y=(125,17)。解做辗转相除法：111257176,7,6qr01231,7,27115,115722,PPPP01230,1,2102,1213,QQQQ31333(1)3,(1)22,xQyP取1253+1722（-）=(125,17)=1则2,,(,)1,,)(,)(,),,abcacabcbciiabcbcbc定理、若是三个整数，且，则（i)与有相同的公因数，（上面假定了至少有一不为零。2.1(,)1,.accabcb推论、若，则121212122.2,,,,,)1nmnmaaabbbaaabbb推论、设及,,是任意两组整数，若前一组中任一整数与后一组中任一整数互质，则(121212,,,(2),,,[,,,nnnaaanndnaaaaaa定义设是个整数，若整数是这个数的倍数，则d就叫作的一个公倍数。所有公倍数中最小的一个叫最小公倍数，记作]。12123[,,,][,,,].nnaaaaaa定理,,,](),,.,,(,)abababiiababababababab定理4设是任意两个正整数，则(i)的所有公倍数就是[的所有倍数；的最小公倍数等于以它们的最大公因数除它们的乘积所得的商，即[]=特别地，