初等数论与中学数学竞赛课件.ppt

资源描述

《初等数论与中学数学竞赛课件.ppt》由会员分享，可在线阅读，更多相关《初等数论与中学数学竞赛课件.ppt（81页珍藏版）》请在三一办公上搜索。

1、初等数论与中学数学竞赛,数学与统计学院陈国慧,一、数论概述,人类从学会计数开始就一直和自然数打交道了，后来由于实践的需要，数的概念进一步扩充，自然数被叫做正整数，而把它们的相反数叫做负整数，介于正整数和负整数中间的中性数叫做0。它们合起来叫做整数。（注：现在，自然数的概念有了改变，包括正整数和0）。对于整数可以施行加、减、乘、除四种运算，叫做四则运算。其中加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行。,数论概述,也就是说，任意两个或两个以上的整数相加、相减、相乘的时候，它们的和、差、积仍然是一个整数。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。人们在对整数进行运算的应

2、用和研究中，逐步熟悉了整数的特性。比如，整数肤浅地划分可分为两大类奇数和偶数（通常被称为单数、双数）；深刻地划分可以分为素数，合数，“1”等。,数论概述,数论这门学科最初就是从研究整数开始的，所以叫做整数论。后来整数论又进一步发展，就叫做数论了。确切的说，数论就是一门研究整数性质的学科。数论这一数学分支，历史悠久，而且有着强大的生命力。数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”.,数论的发展简况,自古以来，数学家对于整数性质的研究一直十分重视，但是直到十九世纪，这些研究成果还只是孤立地记载在各个时期的算术著作中，也就是

3、说还没有形成完整统一的学科。我国古代，许多著名的数学著作中都有关于数论内容的论述，比如求最大公约数、勾股数组、某些不定方程整数解的问题等等。在国外，古希腊时代的数学家对于数论中一个最基本的问题整除性问题就有系统的研究，关于质数、合数、因数、倍数等一系列概念也已经被提出来应用了。,后来的各个时代的数学家也都对整数性质的研究做出过重大的贡献，使数论的基本理论逐步得到完善。在整数性质的研究中，人们发现质数是构成正整数的基本“材料”，要深入研究整数的性质就必须研究质数的性质。因此关于质数性质的有关问题，一直受到数学家的关注。到了十八世纪末，历代数学家积累的关于整数性质零散的知识已经十分丰富了，把它们整

4、理加工成为一门系统的学科的条件已经完全成熟了。,德国数学家高斯集中前人的大成，写了一本书叫做算术探讨，1800年寄给了法国科学院，但是法国科学院拒绝了高斯的这部杰作，高斯只好在1801年自己发表了这部著作。这部书开始了现代数论的新纪元。在算术探讨中，高斯把过去研究整数性质所用的符号标准化了，把当时现存的定理系统化并进行了推广，把要研究的问题和已知的方法进行了分类，还引进了新的方法。,数论的基本内容,数论形成了一门独立的学科后，随着数学其他分支的发展，研究数论的方法也在不断发展。如果按照研究方法来说，可以分成初等数论、解析数论、代数数论和几何数论四个部分。初等数论是数论中不求助于其他数学学科的帮

5、助，只依靠初等的方法来研究整数性质的分支。比如中国古代有名的“中国剩余定理”，就是初等数论中很重要的内容。,关于“中国剩余定理”:公元4-5世纪之交的孙子算经中有一个有趣的问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问：物几何？”秦九韶对同余方程组进行了系统的理论研究，在数书九章中创立了称之为大衍求一术的一整套算法，即把上述问题的解法推广至盛誉中外的“中国剩余定理”-孙子定理。,解析数论是使用数学分析作为工具来解决数论问题的分支。数学分析是以函数作为研究对象的、在极限概念的基础上建立起来的数学学科。用数学分析来解决数论问题是由欧拉奠基的，俄国数学家车比雪夫等也对它的发展做

6、出过贡献。解析数论是解决数论中艰深问题的强有力的工具。比如，对于“质数有无限多个”这个命题，欧拉给出了解析方法的证明，其中利用了数学分析中有关无穷级数的若干知识。,二十世纪三十年代，苏联数学家维诺格拉多夫创造性的提出了“三角和方法”，这个方法对于解决某些数论难题有着重要的作用。我国数学家陈景润在解决“哥德巴赫猜想”问题中使用的是解析数论中的筛法。,代数数论是把整数的概念推广到代数整数的一个分支。数学家把整数概念推广到一般代数数域上去，相应地也建立了素整数、可除性等概念。几何数论是由德国数学家、物理学家闵可夫斯基等人开创和奠基的。几何数论研究的基本对象是“空间格网”。什么是空间格网呢？在给定的直

7、角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对几何学和结晶学有着重大的意义。由于几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。,数论是一门高度抽象的数学学科，长期以来，它的发展处于纯理论的研究状态，它对数学理论的发展起到了积极的作用。但对于大多数人来讲并不清楚它的实际意义。由于近代计算机科学和应用数学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合论等方面都广泛使用了初等数论范围内的许多研究成果；有文献报道，现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅立叶变换等。,此外，数论的许多比较深刻的研究成果也在近似分

8、析、差集合、快速变换等方面得到了应用。特别是现在由于计算机的发展，用离散量的计算去逼近连续量而达到所要求的精度已成为可能。数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。下面简要列出几颗“明珠”：费尔马大定理、孪生素数问题、歌德巴赫猜想、圆内整点问题、完全数问题,费尔马大定理：起源于三百多年前，挑战人类3个世纪，多次震惊全世界，耗尽人类众多最杰出大脑的精力，也让千千万万业余者痴迷。终于在1994年被安德鲁怀尔斯攻克。古希腊的丢番图写过一本著名的“算术”，经历中世纪的愚

9、昧黑暗到文艺复兴的时候，“算术”的残本重新被发现研究。1637年，法国业余大数学家费尔马（Pierre de Fremat）在“算术”的关于勾股数问题的页边上，写下猜想：an+bn=cn是不可能的（这里n大于2；a，b，c，n都是非零整数)。此猜想后来就称为费尔马大定理。,费尔马还写道“我对此有绝妙的证明，但此页边太窄写不下”。一般公认，他当时不可能有正确的证明。猜想提出后，经欧拉等数代天才努力，200年间只解决了n3,4,5,7四种情形。1847年，库木尔创立“代数数论”这一现代重要学科，对许多n（例如100以内）证明了费尔马大定理，是一次大飞跃。,历史上费尔马大定理高潮迭起，传奇不断。其惊

10、人的魅力，曾在最后时刻挽救自杀青年于不死。他就是德国的沃尔夫斯克勒，他后来为费尔马大定理设悬赏10万马克（相当于现在160万美元多），期限19082007年。无数人耗尽心力，空留浩叹。最现代的电脑加数学技巧，验证了400万以内的N，但这对最终证明无济于事。1983年德国的法尔廷斯证明了：对任一固定的n，最多只有有限多个a，b，c振动了世界，获得费尔兹奖（数学界最高奖）。,历史的新转机发生在1986年夏，贝克莱瑞波特证明了:费尔马大定理包含在“谷山丰志村五朗猜想”之中。童年就痴迷于此的怀尔斯，闻此立刻潜心于顶楼书房7年，曲折卓绝，汇集了20世纪数论所有的突破性成果。终于在1993年6月23日剑桥

11、大学牛顿研究所的“世纪演讲”最后，宣布证明了费尔马大定理。立刻震动世界，普天同庆。不幸的是，数月后逐渐发现此证明有漏洞，一时更成世界焦点。,这个证明体系是千万个深奥数学推理连接成千个最现代的定理、事实和计算所组成的千百回转的逻辑网络，任何一环节的问题都会导致前功尽弃。怀尔斯绝境搏斗，毫无出路。1994年9月19日，星期一的早晨，怀尔斯在思维的闪电中突然找到了迷失的钥匙：解答原来就在废墟中！他热泪夺眶而出。怀尔斯的历史性长文“模椭圆曲线和费尔马大定理”1995年5月发表在美国数学年刊第142卷，实际占满了全卷，共五章，130页。1997年6月27日，怀尔斯获得沃尔夫斯克勒10万马克悬赏大奖。离截

12、止期10年，圆了历史的梦。他还获得沃尔夫奖(1996.3），美国国家科学家院奖（1996.6），费尔兹特别奖（1998.8）。,孪生素数问题：,孪生素数是指一对素数，它们之间相差2。例如3和5，5和7，11和13，10016957和10016959等等都是孪生素数。孪生素数猜想，即是否存在无穷多对孪生素数，是数论中未解决的一个重要问题。哈代-李特尔伍德猜想（Hardy-Littlewood conjecture）是孪生素数猜想的一个增强形式，猜测孪生素数的分布与素数定理中描述的素数分布规律相类似。1900年希尔伯特在国际数学家大会上说有了素数公式，哥德巴赫猜想和孪生素数猜想都可以得到解决。,素

13、数定理,素数定理描述素数的大致分布情况。素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义(x)为不大于x的素数个数。数学家找到了一些函数来估计(x)的增长。以下是第一个这样的估计。(x)x/ln x 其中ln x为x的自然对数。上式的意思是当x趋近，(x)和x/ln x的比趋近1.（注：该结果为高斯所发现）。,歌德巴赫猜想：,哥德巴赫猜想的由来1729年1764年，哥德巴赫与欧拉保持了长达三十五年的书信往来。在1742年6月7日给欧拉的信中，哥德巴赫提出了一个命题。他写道：我的问题是这样的：随便取某一个奇数，比

14、如77，可以把它写成三个素数之和：77=53+17+7；再任取一个奇数，比如461，461=449+7+5，也是三个素数之和，461还可以写成257+199+5，仍然是三个素数之和。这样，我发现：任何大于5的奇数都是三个素数之和。,歌德巴赫猜想：,但这怎样证明呢？虽然做过的每一次试验都得到了上述结果，但是不可能把所有的奇数都拿来检验，需要的是一般的证明，而不是个别的检验。欧拉回信说：“这个命题看来是正确的”。但是他也给不出严格的证明。同时欧拉又提出了另一个命题：任何一个大于2的偶数都是两个素数之和，但是这个命题他也没能给予证明。不难看出，哥德巴赫的命题是欧拉命题的推论。,歌德巴赫猜想,事实上，

15、任何一个大于5的奇数都可以写成如下形式：2N+1=3+2(N-1)，其中2(N-1)4。若欧拉的命题成立，则偶数2N可以写成两个素数之和，于是奇数2N+1可以写成三个素数之和，从而，对于大于5的奇数，哥德巴赫的猜想成立。但是哥德巴赫的命题成立并不能保证欧拉命题的成立。因而欧拉的命题比哥德巴赫的命题要求更高。现在通常把这两个命题统称为哥德巴赫猜想。即1.每个不小于6的偶数都可以表示为两个奇素数之和；2.每个不小于9的奇数都可以表示为三个奇素数之和。,中国数学家的贡献,华罗庚是中国最早从事哥德巴赫猜想的数学家。19361938年，他赴英国剑桥大学留学，在哈代的指导下从事数论研究，并开始研究哥德巴赫

16、猜想，取得了很好的成果，证明了对于“几乎所有”的偶数，猜想（1）都是正确的。1950年，华罗庚从美国回国，在中科院数学研究所组织数论研究讨论班，选择哥德巴赫猜想作为讨论的主题，倡议并指导他的一些学生研究这一问题。,他曾对学生们说：“我并不是要你们在这个问题上作出成果来。我的着眼点是哥德巴赫猜想跟解析数论中所有的重要方法都有联系，以哥德巴赫猜想为主题来学习，将可以学会解析数论中所有的重要方法哥德巴赫猜想真是美极了，现在还没有一个方法可以解决它。”参加这个数论讨论班的学生有王元、潘承洞和陈景润等。,出乎华罗庚的意料，学生们在哥德巴赫猜想的证明上取得了相当好的成绩。1956年，王元证明了“34”；同

17、年，原苏联数学家阿维诺格拉朵夫证明了“33”；1957年，王元又证明了“23”；潘承洞于1962年证明了“15”；1963年，潘承洞、巴尔巴恩与王元又都证明了“14”；1966年，陈景润在对筛法作了新的重要改进后，证明了“12”。,1974年，由英国数学家哈勃斯坦和西德数学家李希特合著的筛法一书出版，书中以“陈氏定理”作为最后一章的标题。书中写道：“我们本章的目的是为了证明陈景润下面的惊人定理，我们在前10章已经付印时才注意到这一结果。从筛法的任何方面来说，它都是光辉的顶点。”华罗庚曾对王元说：“在我的学生的工作中，最使我感动的是12。,初等数论与中学教学,在中学数学学习过程中，初等数论的知识

18、和思想方法是常见的。在普通高中数学课程标准中，初等数论初步是作为选修课程系列4的一个专题，教师在日常教学中要给予足够的重视。随着新课程改革的逐步深入，初等数论知识和思想方法，一方面出现在日常教学中，另一方面是以竞赛的形式出现的，后者更为突出。对于前者课标是这样要求的，该专题是为对数学有兴趣和希望进一步提高数学素养的学生而设置的，所涉及的内容反映了某些重要的数学思想方法，有助于学生进一步打好数学基础，提高应用意识，有助于学生终身的发展，有助于扩展学生的数学视野，有助于提高学生对数学的科学价值、应用价值、文化价值的认识。,初等数论与中学教学,对于后者，初等数论在奥林匹克竞赛中占有愈来愈重要的地位，

19、对提高中学生的数学素养很有帮助。有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了。任何学生，如能把当今任何一本数论教材中的习题做出，就应当受到鼓励，并劝他将来从事数学方面的工作。”所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的比重。,初等数论与中学教学,致力于数学竞赛的教师而言，必须明确数论的基本结构，它包括整除理论，同余理论和不定方程。整除理论是初等数论的基础，它是在带余除法的基础上建立起来的，整除理论的中心内容是算术基本定理和最大公因数理论。同余理论是初等数论的核心，它是数论所特有的思想、概念与方法。从历史来看，求解不定方程是推进数论发展的最重要的课题，它是建立在

21、,其中|a|是a的绝对值,当a0时|a|=a;当a0时|a|=-a.若a|b,则(-a)|b,a|(-b),(-a)|(-b),|a|b|.证明只证明,余下不难证明.因为a|b且a|c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),所以,a|(bm+cn).,因数和倍数,定理若 a是b的真因数,则 1|a|b|.定理若a为是整数,且|a|b|,|b|a|,则 a=0.证明因为|b|a|,故有整数q,使得|a|=|b|q.若|a|=0,则a=0.若|a|0,则由于 00,则由 q是整数而有q1.由|a|=|b|和q1有|a|b|,这与|a|b|矛盾,故q=0;若q=0

22、和|a|=|b|q有a=0.,因数和倍数,定理(带余除法)若a为是二个整数,b0,则唯一存在两个整数q和r,使得下式成立:a=bq+r,0r|b|.,素数和合数,在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除定义一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用p或p1,p2,来表示.,最大公因数和最小公倍数,定义设al,a2,an和d都是正整数,n2.若d|ai,1in,则称d是al,a2,an.的公因数.在公因数中最大的那一个数,称为al,a2,an的最大公因数,记为gcdal,a2,a

23、n.(greatest common divisor)或者(al,a2,an).若gcd(al,a2,an)=1,称al,a2,an是互素的.,最大公因数和最小公倍数,定理设a和b都是正整数,且ab,a=bq+r 0rb其中q和r都是正整数.则:a和b的任一公因数也是b和r的公因数；b和r的任一公因数也是a和b的公因数；(a,b)=(b,r);若(a,b)=d,则(a|d,b|d)=1.,整数分解唯一性定理,定理(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.若a=2,则2为素数,从而2即所求分解式.现在假

24、设小于a的每个正整数均可分解成有限个素数之积.考虑a,若a是素数,则证毕.否则a便有真因数d,而a=cd,其中c和d均是大于1的正整数,并且c和 d均小于a.由归纳假设,c和 d均有分解式c=p1p2pk和d=q1q2ql,其中p1,p2,pk,ql,q2,ql均是素数.因此a=cd=p1p2,pkqlql;即为所求的分解式,整数分解唯一性定理,再证唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数 a,假设 a有两个分解式 a=plp2pk和a=q1q2ql,其中pl,p2,pk和q1,q2,ql都是素数.于是p1|q1q2ql,根据定理7.4.7知必有

25、一qi,使得p1|qi.不妨令i=1,即p1|q1,显然p1=q1.令a=a/p1,则a=p2p3pk,aq2q2ql.若a=1,则a=p1=q1,即a的分解式唯一.若a1,注意到aa,从而由归纳假设知,a的分解式是唯一的.因此k=l,并且 p1=q1,pk=qk,再由p1=ql,知a分解式也是唯一的.,整数分解唯一性定理,若将n的分解式中相同素因数合并为它的幂数,则任意大于1的整数a只能分解成一种形式:,n1,其中p1,p2,pn是互不相同的素数,al,a2,an是正整数.并称(1)是 a的标准分解式.,函数x与x,定义设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，又称x=x

26、-x为x的小数部分。,函数x与x,函数x与x,不定方程,不定方程：未知数个数多于方程个数，且对解有一定限制（比如要求解为正整数等）的方程。是数论中最古老的分支之一。古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。,研究不定方程要解决三个问题：判断何时有解。有解时决定解的个数。求出所有的解。中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的张丘建算经中的百鸡问题标志中国对不定方程理论有了系统研究。秦九韶的大衍求一术将不定方程与同余理论联系起来。百鸡问题说：“鸡翁一，直钱五，鸡母一，直钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、

27、雏各几何？”。设x，y，z分别表鸡翁、母、雏的个数，则此问题即为不定方程组的非负整数解x，y，z，这是一个三元不定方程组问题。,不定方程问题的常见类型（1）求不定方程的解；（2）判定不定方程是否有解；（3）判定不定方程的解的个数（有限个还是无限个）。,解不定方程问题常用的解法（1）代数恒等变形：如因式分解、配方、换元等；（2）不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解；（3）同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解；（4）构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解；（5）无穷递推法

28、。一些特殊方程的求解方法,同余理论,定义给定一正整数m,若用m去除两个整数a和b所得余数相同,则称a为对模m同余,记作ab(mod m);若余数不同,则称 a为对模m不同余,记作ab(mod m).显然，a0(mod m)iff m|a.由同余的定义,可得下列简单性质:自反性:aa(mod m).对称性:若ab(mod m),则 ba(mod m).传递性:若ab(mod m),bc(mod m),则:ac(mod m).可见,同余关系是等价关系.,同余理论,定理整数a,b对模m同余，若m|(a-b),即:ab(mod m),若 m|(a-b).证明设ab(mod m),则a=mq1+r

30、余理论,证明因为m|(a-b),m|(c-d),故有m|x(a-b)+y(c-d)=(ax+cy)-(bx+dy).由 m|(a-b)+b(c-d)=ac-bd立即可得.由于 a-b=mq,其中 q是一整数,因此:an=(b+mq)n=bn+Cn1bn-1(mq)1+Cnn-1b1(mq)n-1+(mq)n=bn+mq,其中:q1是一整数.所以,anbn(mod m).由和可证.,同余式定义和基本性质,定理正整数a能被9整除，若 9整除a的十进制表示各数字的和则由10i1(mod 9)(i=1,2,n)和定理可得:,同余理论,定理若ac=bc(mod m),(c,m)=d,则 a b(mo

31、d(m/d)证明因为m|c(a-b),于是(m/d)|(a-b)(c/d),又因为(c,m)=d,则有(c/d,m/d)=1,因此由定理7.4.2知,(m/d)|(a-b),即:a b(mod(m/d).显然,由本定理可得如下推论.推论若 ac=bc(mod m),(c,m)=1,则:ab(mod m).,同余理论,定理若ab(mod m),且d|m,则:ab(mod m).若ab(mod m),则(a,m)=(b,m).ab(mod mi),(1in),iff ab(mod m1,m2,mn).证明只给出的证明,和读者完成.必要性:由知,是成立的.充分性:若a b(mod mi),1

32、in,则:mi|(a-b),1in,即(a-b)是m1,m2,mn的公倍数,从而也是m1,m2,mn的倍数,因此:ab(mod m1,m2,mn).,不定方程,以下题目选自1998年2008年全国初中数学联赛试题、初一、初二数学希望杯竞赛试题（部分）,有关整除的问题,有关整除的问题,有关整除的问题,有关整除的问题,解：设这11个连续奇数为：2n+1，2n+3，2n+5，2n+21则(2n+1)+(2n+3)+(2n+5)+(2n+21)=1991即 11(2n+11)=1991解得n=85第六个数是285+11=181,有关整除的问题,（竞赛题4）.某自然数的平方是一个四位数，千位数字是4，个

33、位数字是5，这个数是_解：由条件知，这个自然数只能是两位数，其个位数字必定是5，它的十位数字可能是6或7。经验算，75的平方等于5625，65的平方等于4225所以，这个数为65,（竞赛题5）.一个自然数n减去59之后是一个完全平方数，加上30之后仍是一个完全平方数，则n=_,有关整除的问题,有关整除的问题,（竞赛题6）.已知a，b，c，d是四个两两不等的正整数，它们的乘积abcd=1995，则a+b+c+d的最大值是_解：abcd=1995=35719=135(719)令a=1，b=3，c=5，d=133a+b+c+d=142为最大,有关整除的问题,（2005年全国初中数学联赛决赛试卷）：从

34、自然数1，2，3，354中任取178个数，试证：其中必有两个数，它们的差是177证明：从1到354的自然数中，任取178个数由于任何数被177除，余数只能是0，1，2，176这177种之一因而178个数中，至少有两个数a，b的余数相同，也即至少有两个数a，b之差是177的倍数，即a-b=k177又因1354中，任两数之差小于2177=354所以两个不相等的数a，b之差必为177即a-b=177从自然数1，2，3，354中任取178个数，其中必有两个数，它们的差是177,二、函数x与x定义1 设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，又称x=x x为x的小数部分。,有关取整函数的问题,有关取整函数的问题,有关取整函数的问题,有关取整函数的问题,有关同余的问题,有关同余的问题,有关同余的问题,有关同余的问题,有关同余的问题,方程的整数解问题,方程的整数解问题,方程的整数解问题,作业,找出整数能被37，101整除的判别条件，并加以证明。,

展开阅读全文