初等数论课件.ppt

1、初等数论初等数论考察的方式：考察的方式：1、平时的作业、报告：、平时的作业、报告：40%2、最后的笔试组成：、最后的笔试组成：60% 一、数论发展史一、数论发展史 数论是研究整数性质的一门很古数论是研究整数性质的一门很古老的数学分支，老的数学分支， 其初等部分是以整其初等部分是以整数的整除性为中心的，包括整除性、数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数不定方程、同余式、连分数、素数（即整数）分布（即整数）分布 以及数论函数等内以及数论函数等内容，统称容，统称初等数论初等数论（Elementary Elementary Number TheoryNumber Theory）

2、。）。 初等数论的大部分内容早在古希腊欧初等数论的大部分内容早在古希腊欧几里德的几里德的 几何原本几何原本中就已出现。欧几中就已出现。欧几里得证明了素数有无穷多个，他还给出求里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，两个自然数的最大公约数的方法， 即所谓即所谓欧几里得算法。我国古代在数论方面亦有欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的杰出之贡献，现在一般数论书中的“中国中国剩余定理剩余定理”正是我国古代正是我国古代孙子算经孙子算经中中的下卷第的下卷第2626题，我国称之为题，我国称之为“孙子定理孙子定理”。 近代初等数论的发展得益于费马、欧近代

3、初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。拉、拉格朗日、勒让德和高斯等人的工作。18011801年，高斯的年，高斯的算术探究算术探究是数论的划是数论的划时代杰作。时代杰作。 “数学是科学之王，数论是数学之王数学是科学之王，数论是数学之王”。 -高斯高斯二二 几个著名数论难题几个著名数论难题 初等数论是研究整数性质的一门学科，历史上遗初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。懂，容易引起人的兴趣，但是解决它们却非常困难。 其中，非常著名

4、的问题有：哥德巴赫猜想其中，非常著名的问题有：哥德巴赫猜想 ；费；费尔马大定理尔马大定理 ；孪生素数问题；孪生素数问题 ；完全数问题等。；完全数问题等。 17421742年年, ,由德国中学教师哥德巴赫在教学中首先发现的。由德国中学教师哥德巴赫在教学中首先发现的。17421742年年6 6月月7 7日，哥德巴赫写信给当时的大数学家欧拉日，哥德巴赫写信给当时的大数学家欧拉, ,正式提正式提出了以下的猜想：出了以下的猜想：1 1、哥德巴赫猜想：、哥德巴赫猜想： 陈景润在陈景润在19661966年证明了年证明了“哥德巴赫猜想哥德巴赫猜想”的的“一个大偶一个大偶数可以表示为一个素数和一个不超过两个素数

5、的乘积之和数可以表示为一个素数和一个不超过两个素数的乘积之和”所谓的所谓的1+21+2，是，是筛法筛法的光辉顶点，至今仍是的光辉顶点，至今仍是“哥德巴赫哥德巴赫猜想猜想”的最好结果的最好结果。 一个大于一个大于6 6的偶数可以表示为不同的两个质数之和。的偶数可以表示为不同的两个质数之和。2 2、费尔马大定理：、费尔马大定理： 费马是十七世纪最卓越的数学家之一，他在数学费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的许多领域中都有极大的贡献，因为他的本行是专业的律师，世人冠以律师，世人冠以“业余王子业余王子”之美称。在三百七十多之美称。在三百七十多年前的某

6、一天，费马正在阅读一本古希腊数学家戴奥年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处，芬多斯的数学书时，突然心血来潮在书页的空白处，写下一个看起来很简单的定理。写下一个看起来很简单的定理。(3)nnnxyzn方方程程无无非非0 0整整数数解解 经过经过8 8年的努力，英国数学家年的努力，英国数学家 安德鲁安德鲁怀尔斯怀尔斯 终于在终于在19951995年完成了该定理的证明。年完成了该定理的证明。3 3、四色问题、四色问题 “任何一张平面地图只用四种颜色就能使具有共同边界任何一张平面地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。的国家着上不同

7、的颜色。”用数学语言表示，即用数学语言表示，即“将平面将平面任意地细分为不相重叠的区域，每一个区域总可以用任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。到相同的数字。”这里所指的相邻区域，是指有一整段边这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。 高速数字计算机的发明，促使更多数学家对

8、高速数字计算机的发明，促使更多数学家对“四色问题四色问题”的研究。电子的研究。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。就在了对四色猜想证明的进程。就在1976年年6月，在美国伊利诺斯大学的两台不月，在美国伊利诺斯大学的两台不同的电子计算机上，用了同的电子计算机上，用了1200个小时，作了个小时，作了100亿判断，结果没有一张地图亿判断，结果没有一张地图是需要五色的，最终证明了四色定理，轰动了世界。是需要五色的，最终证明了四色定理，轰动了世界。 这是一百多年来吸引许多数学家与数

9、学爱好者的大事，当两位数学家这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了了“四色足够四色足够”的特制邮戳，以庆祝这一难题获得解决。的特制邮戳，以庆祝这一难题获得解决。 1852年，毕业于伦敦大学的格斯里（年，毕业于伦敦大学的格斯里（FrancisGuthrie）来到一家科研单）来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。这个现象位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。这个现象能不能从数学上加以严格证明呢？

10、他和他正在读大学的弟弟决心试一试，能不能从数学上加以严格证明呢？他和他正在读大学的弟弟决心试一试，但是稿纸已经堆了一大叠，研究工作却是没有任何进展。但是稿纸已经堆了一大叠，研究工作却是没有任何进展。3 3、四色问题、四色问题 孪生素数就是指相差2的素数对，例如3和5，5和7，11和13。孪生素数猜想正式由希尔伯特在1900年国际数学家大会的报告上第8个问题中提出，可以这样描述：存在无穷多个素数p，使得p + 2是素数。素数对（p, p + 2）称为孪生素数。 在1849年，阿尔方波利尼亚克提出了一般的猜想：对所有自然数k，存在无穷多个素数对（p, p + 2k）。k = 1的情况就是孪生素数猜

11、想；k=2 (即间隔为4) 的素数对被称为 cousin prime ；而 k=3 (即间隔为 6) 的素数对竟然被称为 sexy prime (不过别想歪了，之所以称为 sexy prime 其实是因为 sex 正好是拉丁文中的 6。) 4 4、孪生素数问题、孪生素数问题 1966年利用筛法 (sieve method) 陈景润证明了： 存在无穷多个素数 p， 使得 p+2 要么是素数， 要么是两个素数的乘积。 一般认为， 由于筛法本身的局限性， 这一结果在筛法范围内很难被超越 2013年，5月14日，自然（Nature）杂志在线报道张益唐证明了“存在无穷多个之差小于7000万的素数对”，这

12、一研究随即被认为在孪生素数猜想这一终极数论问题上取得了重大突破，甚至有人认为其对学界的影响将超过陈景润的“1+2”证明。 5 5、最完美的数、最完美的数完全数问题完全数问题 下一个具有同样性质的数是下一个具有同样性质的数是28, 28=1+2+4+7+14.28, 28=1+2+4+7+14.接着是接着是496496和和8128.8128.他们称这类数为完美数他们称这类数为完美数. . 欧几里德在大约公元前欧几里德在大约公元前350-300350-300年间证明了年间证明了: : 注意以上谈到的完全数都是注意以上谈到的完全数都是偶完全数偶完全数, ,至今仍然至今仍然不知道有没有不知道有没有奇完

13、全数奇完全数。 完美数又称为完全数完美数又称为完全数, ,最初是由毕达哥拉斯的信最初是由毕达哥拉斯的信徒发现的徒发现的, ,他们注意到他们注意到, ,数数6 6有一个特性有一个特性, ,它等于它自它等于它自己的因子己的因子( (不包括它自身不包括它自身) )的和，的和， 如：如：6=1+2+3.6=1+2+3.1212(21)nnn 若若是是素素数数，则则是是完完全全数数三、我国古代数学的伟大成就三、我国古代数学的伟大成就 公元前公元前100100多年，汉朝人撰，是一部既谈天体又多年，汉朝人撰，是一部既谈天体又谈数学的天文历算著作，主要讨论盖天说，提出了谈数学的天文历算著作，主要讨论盖天说，提

14、出了著名的著名的“勾三股四弦五勾三股四弦五”这个勾股定理的一个特例。这个勾股定理的一个特例。1 1、周髀算经、周髀算经2 2、孙子算经、孙子算经 约成书于四、五世纪，作者生平和编写年代都不约成书于四、五世纪，作者生平和编写年代都不清楚。现在传本的清楚。现在传本的孙子算经孙子算经共三卷。卷上叙述算共三卷。卷上叙述算筹记数的纵横相间制度和筹算乘除法则，卷中举例说筹记数的纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算法和筹算开平方法。卷下第明筹算分数算法和筹算开平方法。卷下第3131题，可谓题，可谓是后世是后世“鸡兔同笼鸡兔同笼”题的始祖，后来传到日本，变成题的始祖，后来传到日本，变成“鹤龟算鹤

15、龟算”。 具有重大意义的是卷下第具有重大意义的是卷下第2626题：今有物不知其数，题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问三三数之剩二，五五数之剩三，七七数之剩二，问物几何？物几何？孙子算经孙子算经不但提供了答案，而且还给不但提供了答案，而且还给出了解法。南宋大数学家秦九韶则进一步开创了对出了解法。南宋大数学家秦九韶则进一步开创了对一次同余式理论的研究工作，推广一次同余式理论的研究工作，推广“物不知数物不知数”的的问题。德国数学家高斯问题。德国数学家高斯1777-18551777-1855于于18011801年出版年出版的的算术探究算术探究中明确地写出了上述定理。中明确

16、地写出了上述定理。18521852年，年，英国基督教士伟烈亚士将英国基督教士伟烈亚士将孙子算经孙子算经中物不知数中物不知数问题的解法传到欧洲，问题的解法传到欧洲，18741874年马蒂生指出孙子的解年马蒂生指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一法符合高斯的定理，从而在西方的数学史里将这一个定理称为个定理称为“中国剩余定理中国剩余定理” 。周髀算经周髀算经孙子算经孙子算经 1983 1983年在湖北省江陵县张家山，出土了一批西汉年在湖北省江陵县张家山，出土了一批西汉初年，即吕后至文帝初年的竹简，共千余支。经初步初年，即吕后至文帝初年的竹简，共千余支。经初步整理，其中有律令、整理

17、，其中有律令、脉书脉书、引书引书、历谱、日、历谱、日书等多种古代珍贵的文献，还有一部数学著作，据写书等多种古代珍贵的文献，还有一部数学著作，据写在一支竹简背面的字迹辨认，这部竹简算书的书名叫在一支竹简背面的字迹辨认，这部竹简算书的书名叫算数书算数书。 算数书算数书是中国现已发现的最古的一部算书，是中国现已发现的最古的一部算书，大约比现有传本的大约比现有传本的九章算术九章算术还要早近二百年，而还要早近二百年，而且且九章算术九章算术是传世抄本或刊书，是传世抄本或刊书，算数书算数书则是则是出土的竹筒算书，属于更可珍贵的第一手资料，所以出土的竹筒算书，属于更可珍贵的第一手资料，所以算数书算数书引起了国

18、内外学者的广泛关注，目前正在引起了国内外学者的广泛关注，目前正在被深入研究之中。被深入研究之中。3 3、算数书、算数书 数术记遗数术记遗相传是汉末徐岳所作，亦有数学史家相传是汉末徐岳所作，亦有数学史家认为本书是北周甄鸾自著。认为本书是北周甄鸾自著。 数术记遗数术记遗把大数的名称按不同的涵义排列三个把大数的名称按不同的涵义排列三个不同的数列，另一部份是关于一个幻方的清楚的说明，不同的数列，另一部份是关于一个幻方的清楚的说明，它成为数论中这一发现的最古的文字记载之一，书中它成为数论中这一发现的最古的文字记载之一，书中至少提到了四种算盘，因此它是谈到算盘的最古老的至少提到了四种算盘，因此它是谈到算盘

19、的最古老的书籍。书籍。 4 4、数术记遗、数术记遗算数书算数书数术记遗数术记遗 中的算盘中的算盘 根据研究，西汉的张苍根据研究，西汉的张苍 、耿寿昌曾经做过增补、耿寿昌曾经做过增补和整理，其时大体已成定本。最后成书最迟在东汉和整理，其时大体已成定本。最后成书最迟在东汉前期。九章算术将书中的所有数学问题分为九大类，前期。九章算术将书中的所有数学问题分为九大类，就是就是“九章九章”。 三国时期的刘徽为三国时期的刘徽为九章九章作注，加上自己心得作注，加上自己心得体会，使其便于了解，可以流传下来。体会，使其便于了解，可以流传下来。 唐代的李淳风又重新做注唐代的李淳风又重新做注(656(656年年) )

20、，作为，作为算数算数十经十经之一，版刻印刷，作为通用教材。之一，版刻印刷，作为通用教材。5 5、九章算术、九章算术 九章算术九章算术的出现，标志着我国古代数学体系的出现，标志着我国古代数学体系的正式确立，当中有以下的一些特点：的正式确立，当中有以下的一些特点：1.1.是一个应用是一个应用数学体系，全书表述为应用问题集的形式；数学体系，全书表述为应用问题集的形式；2.2.以算法以算法为主要内容，全书以问、答、术构成，为主要内容，全书以问、答、术构成，“术术”是主要是主要需阐述的内容；需阐述的内容；3.3.以算筹为工具。以算筹为工具。 九章算术九章算术取得了多方面的数学成就，包括：取得了多方面的数

21、学成就，包括：分数运算、比例问题、双设法、一些面积、体积计算、分数运算、比例问题、双设法、一些面积、体积计算、一次方程组解法、负数概念的引入及负数加减法则、一次方程组解法、负数概念的引入及负数加减法则、开平方、开立方、一般二次方程解法等。开平方、开立方、一般二次方程解法等。九章算术九章算术的思想方法对我国古代数学产生了巨大的影响。自的思想方法对我国古代数学产生了巨大的影响。自隋唐之际，隋唐之际，九章算术九章算术已传入朝鲜、日本，现在更已传入朝鲜、日本，现在更被译成多种文字。被译成多种文字。 海岛算经海岛算经由三国刘徽所着，最初是附于他所由三国刘徽所着，最初是附于他所注的注的九章算术九章算术（2

22、63263）之后，唐初开始单行，体）之后，唐初开始单行，体例亦是以应用问题集的形式。例亦是以应用问题集的形式。 全书共全书共9 9题，全是利用测量来计算高深广远的问题，全是利用测量来计算高深广远的问题，首题测算海岛的高、远，故得名。题，首题测算海岛的高、远，故得名。海岛算经海岛算经是中国最早的一部测量数学事着，亦为地图学提供了是中国最早的一部测量数学事着，亦为地图学提供了数学基础。数学基础。6、海岛算经、海岛算经7 7、算经十书、算经十书 唐代国子监内设立算学馆，置博士、助教指导唐代国子监内设立算学馆，置博士、助教指导学生学习数学，规定学生学习数学，规定周髀算经周髀算经、九章算术九章算术、孙子

23、算经孙子算经、五曹算经五曹算经、夏侯阳算经夏侯阳算经、张丘建算经张丘建算经、海岛算经海岛算经、五经算术五经算术、缀术缀术、缉古算经缉古算经十部算经为课本，用以进行十部算经为课本，用以进行数学教育和考试，后世通称为算经十书算经十书是数学教育和考试，后世通称为算经十书算经十书是中国汉唐千余年间陆续出现的十部数学著作北宋时中国汉唐千余年间陆续出现的十部数学著作北宋时期（期（10841084年），曾将一部算经刊刻发行，这是世界上年），曾将一部算经刊刻发行，这是世界上最早的印刷本数学书（此时最早的印刷本数学书（此时缀术缀术已经失传，实已经失传，实际刊刻的只有九种）。际刊刻的只有九种）。 8 8、测圆海镜

24、、测圆海镜测圆海镜测圆海镜由中国金、元时期数学家李冶所著，成书于由中国金、元时期数学家李冶所著，成书于12481248年。全书共有年。全书共有1212卷，卷，170170问。这是中国古代论述容圆的一问。这是中国古代论述容圆的一部专箸，也是天元术的代表作。部专箸，也是天元术的代表作。测圆海镜测圆海镜所讨论的问题所讨论的问题大都是已知勾股形而求其内切圆、旁切圆等的直径一类的问大都是已知勾股形而求其内切圆、旁切圆等的直径一类的问题。在题。在测圆海镜测圆海镜问世之前，我国虽有文字代表未知数用问世之前，我国虽有文字代表未知数用以列方程和多项式的工作，但是没有留下很有系统的记载。以列方程和多项式的工作，但

25、是没有留下很有系统的记载。李冶在李冶在测圆海镜测圆海镜中系统而概栝地总结了天元术，使文中系统而概栝地总结了天元术，使文词代数开始演变成符号代数。词代数开始演变成符号代数。 所谓天元术，就是设所谓天元术，就是设“天元天元一一”为未知数，根据问题的已知条件，列出两个相等的多项为未知数，根据问题的已知条件，列出两个相等的多项式，经相减后得出一个高次方式程，称为天元开方式，这与式，经相减后得出一个高次方式程，称为天元开方式，这与现代设现代设x为未知数列方程一样。欧洲的数学家，到了为未知数列方程一样。欧洲的数学家，到了1616世纪以世纪以后才完全作到这一点。后才完全作到这一点。测圆海镜测圆海镜费马费马

26、法法1601-16651601-1665，是数学史上，是数学史上最伟大的业余数学家，提出了费马最伟大的业余数学家，提出了费马大、小定理；在坐标几何，无穷小，大、小定理；在坐标几何，无穷小，概率论等方面有巨大贡献。概率论等方面有巨大贡献。哥德巴赫哥德巴赫 1690-17641690-1764， 德国数学家；曾担任中学德国数学家；曾担任中学教师，教师，17251725年到俄国，年到俄国，被选为彼得堡科学院院士被选为彼得堡科学院院士. .希尔伯特希尔伯特 德德1862186219431943，他领，他领导的数学学派是导的数学学派是1919世纪末世纪末2020世纪世纪初数学界的一面旗帜，希尔伯特初数学

27、界的一面旗帜，希尔伯特被称为被称为“数学界的无冕之王数学界的无冕之王”。著著数论报告数论报告、几何基础几何基础、线性积分方程一般理论基础线性积分方程一般理论基础. .华罗庚华罗庚1910198519101985，是中国解析，是中国解析数论、矩阵几何学、典型群、自数论、矩阵几何学、典型群、自安函数论等多方面研究的创始人安函数论等多方面研究的创始人和开拓者。以华氏命名的数学科和开拓者。以华氏命名的数学科研成果很多。被列为芝加哥科学研成果很多。被列为芝加哥科学技术博物馆中当今世界技术博物馆中当今世界8888位数学位数学伟人之一。伟人之一。 陈景润陈景润1933193319961996，主要研究，主要

28、研究解析数论，他研究哥德巴赫猜解析数论，他研究哥德巴赫猜想和其他数论问题的成就，至想和其他数论问题的成就，至今仍然在世界上遥遥领先。其今仍然在世界上遥遥领先。其成果也被称之为陈氏定理。成果也被称之为陈氏定理。王元王元193019305050年代至年代至6060年年代初，首先在中国将筛法代初，首先在中国将筛法用于哥德巴赫猜想研究，用于哥德巴赫猜想研究，并证明了命题并证明了命题3+43+4，19571957年年又证明又证明2+32+3，这是中国学者，这是中国学者首次在此研究领域跃居世首次在此研究领域跃居世界领先地位界领先地位. . 数论是以严格和简洁著称，内容既丰富数论是以严格和简洁著称，内容既丰

29、富又深刻。我将会介绍数论中最基本的概念又深刻。我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过一些基本概念，并且对中小学时代学习过一些基本概念，例如整除性、最大公因子、最小公倍数、例如整除性、最大公因子、最小公倍数、辗转相除法等，有一定的了解。辗转相除法等，有一定的了解。第一章 整数的整除性第一节 整除的概念l一、基本概念一、基本概念 1、自然数、整数 2、正整数、负整数 3、奇数、偶数l一个性质一个性质： 整数+整数=整数 整数-整数=整数 整数 整数=整数 关于奇数和偶数性质关于奇数和偶数性质：1 1、奇数、奇数

30、+ +奇数奇数=偶数；偶数； 奇数奇数+ +偶数偶数=奇数；奇数； 偶数偶数+ +偶数偶数=偶数；偶数；2、两个数之和是奇（偶）数，则这两个数的、两个数之和是奇（偶）数，则这两个数的奇偶性相反（同）。奇偶性相反（同）。3 3、若干个整数之和为奇数，则这些数中必、若干个整数之和为奇数，则这些数中必有奇数，且奇数的个数为奇数个；若干个整有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，则这些数中若有奇数，奇数数之和为偶数，则这些数中若有奇数，奇数的个数必为偶数个。的个数必为偶数个。关于奇数和偶数性质：关于奇数和偶数性质：4 4、奇数、奇数奇数奇数=奇数；奇数； 奇数奇数偶数偶数=偶数；偶数； 偶

31、数偶数偶数偶数=偶数；偶数；5、若干个整数之积为奇数，则这些数必为奇数；、若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中至少有一若干个整数之积为偶数，则这些数中至少有一个是偶数。个是偶数。6、若、若a是整数，则是整数，则|a| 与与a 有相同的奇偶性。有相同的奇偶性。7.若若a ，b 是整数，则是整数，则a +b 与与a -b 奇偶性相同。奇偶性相同。例例1 在在1,2,3， ，1998,1999这这1999个数个数的前面任意添加一个正号或负号，问它们的的前面任意添加一个正号或负号，问它们的代数和是奇数还是偶数？代数和是奇数还是偶数？解：在这1999个数里面，有100

32、0个奇数，999个偶数，由于偶数个奇数相加减值为奇数，偶数相加减值为偶数，偶数和偶数的和奇数，所以结果为偶数。例例2 2 设设n n 为奇数，为奇数， 是是1,21,2， ，n n 的任意一个排列，证明的任意一个排列，证明 必是偶数。必是偶数。12,naaa12(1)(2)()naaan是偶数中必至少有一个偶数，是偶数是奇数其中的任意一个排列，是证明：)() 1)(1()() 1() 1(0)() 1() 1(21,2 , 1,2121212121naaanaaanaaanaaannaaannnnn不是完全平方数同理，不是完全平方数此时得不妨设为奇数为正整数，为完全平方数，注意到假设都为完全平

33、方数证明：显然1134101015, 122) 12(12121-2641135 ,251132 , 91-52222dnndnndndddd例4 设正整数d 不等于2,5,13，证明集合 中可以找到两个数a ，b ，使得a b-1 不是完全平方数。d,13, 5 , 2二、整除l1、定义：设a，b是整数，b0。如果存在一个整数q使得等式： a=bq 成立，则称b能整除a或a能被b整除，记b a；如果这样的q不存在，则称b不能整除a，记为b a。 注：显然每个非零整数注：显然每个非零整数a都有约数都有约数 1， a，称这四个，称这四个数为数为a的平凡约数，的平凡约数，a的另外的约数称为非平凡约

34、数。的另外的约数称为非平凡约数。| 素数：素数：定义：定义：设整数设整数n0n0，1.1.如果除了显然因数如果除了显然因数1 1，n n以外，以外，n n没有其他因数，那么，没有其他因数，那么，n n叫叫做素数（或质数或不可约数），否则，做素数（或质数或不可约数），否则，n n叫叫做合数做合数. .规定：若没有特殊说明，素数总是指正整规定：若没有特殊说明，素数总是指正整数，通常写成数，通常写成p p或或 p p1 1， p p2 2， p pn n. . 例如：整数例如：整数2 2，3 3，5 5，7 7都是素数，而整数都是素数，而整数4 4，6 6，8 8，1010，2121都是合数都是合数

35、. .2、整除的性质 设a，b，c是整数 （1）a a （2）如果 a b ， b c ，则a c （3）如果 a b ， a c ,则对任意整数m，n 有a mb+cn. （4）如果a c ，则对任何整数b ， a b c. （5）若（ a，b ）=1，且a b c，则a c （6）若（ a，b ）=1，且a c， b c则a b c （7）若（ a，b ）=1，且a b c，则a c， b c （1）设p为素数 ，若p b a ，则p a 或 p b .（2） p|a 或 (p，a)=1 . p pa 常用结论：常用结论：（4） 任何大于任何大于1的整数的整数a都至少有一个素约数。都至少有

36、一个素约数。推论推论 任何大于任何大于1的合数的合数a必有一个不超过必有一个不超过 的素约数。的素约数。a2a例例6 证明：证明：121 ，n Z。 2212nn 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 11 11 1212 1313 1414 1515 1616 1717 1818 1919 2020 2121 2222 2323 2424 2525 2626 2727 2828 2929 3030 3131 3232 3333 3434 3535 3636 3737 3838 3939 4040 4141 4242 4343 4444 4545 4

37、646 4747 4848 4949 5050 5151 5252 5353 5454 5555 5656 5757 5858 5959 6060 61 61 6262 6363 6464 6565 6666 6767 6868 6969 7070 7171 7272 7373 7474 7575 7676 7777 7878 7979 8080 8181 8282 8383 8484 8585 8686 8787 8888 8989 8080 9191 9292 9393 9494 9595 9696 9797 9898 9999 100100 ) 12.22)(12(12)2() 1(ab

38、ababab可除性判别方法l判别方法1：（整数被2整除） 如果一个整数的末尾数字能被2整除，则该数能被2整除。即：若2 a0，则2 N.l判别方法2：（整数被5整除） 如果一个整数的末尾数字能被5整除，则该数能被5整除。即：若5 a0，则5 N.l判别方法3：（整数被3整除） 如果一个整数的各位数字之和能被3整除，则该数能被3整除。即：若3 an+an-1+a1+a0，则3 N.l判别方法4：（整数被9整除）如果一个整数的各位数字之和能被9整除，则该数能被9整除。即：若9 an+an-1+a1+a0，则9 N.l例例6 6 有一个自然数乘以有一个自然数乘以9 9后，得到一个仅由数字后，得到一个

39、仅由数字1 1组组成的多位数，求这个自然数最小为多少？成的多位数，求这个自然数最小为多少？ 12345679 12345679 l判别方法5：（整数被4或25整除） 如果一个数的末两位数能被4或25整除，那么，这个数就一定能被4或25整除l判别方法6：（整数被8或125整除） 如果一个数的末三位数能被8或125整除，那么，这个数就一定能被8或125整除可除性判别方法可除性判别方法l判别方法7：（整数被11整除） (1) 如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果 ，则11N.(2)把一个数由右边向左边数,将奇

40、位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除。例如：判断491678能不能被11整除。 奇位数字的和9+6+8=23 ，偶位数位的和4+1+7=12 ，23-12=11因此,491678能被11整除。这种方法叫“奇偶位差法”。可除性判别方法l判别方法8：（整数被13整除） 如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被13整除，则该整数能13整除.即如果 ， 则13N.判别方法9：（整数被7整除）（适用于数字位数少时）一个数割去末位数字，再从留下来的数中减去所割去数字的2倍，

41、这样，一次次减下去，如果最后的结果是7的倍数（包括0），那么，原来的这个数就一定能被7整除例如：判断133是否7的倍数的过程如下：13327，所以133是7的倍数 例例7 7 设设a a，b b，c c是三个互不相等的正整数，是三个互不相等的正整数，求证：求证：三数中至少有一个能被三数中至少有一个能被1010整除。整除。333333,a bab b cbc c aca例例8 设设n 为自然数，求证：为自然数，求证：能被能被1985整除。整除。3237632855235nnnnA例例9 设设p为大于为大于5的素数的素数 ，求证：求证：24041p 例例10 p 5是素数是素数 ，且，且2 p +

42、1也是素数，证也是素数，证明：明： 4 p +1必是合数。必是合数。例例11 请确定最小正整数请确定最小正整数A，其末位数为，其末位数为6，若将末位的若将末位的6移至首位，其余数字不变，则移至首位，其余数字不变，则为原数的为原数的4倍。倍。例例12 一个正整数，如果用一个正整数，如果用7进位制进位制表示，则为表示，则为 ，如果用，如果用5进位制进位制表示为表示为 ，请用，请用10进位制表示进位制表示此数。此数。x y zzy x例例13 证明：对任何自然数证明：对任何自然数n 和和k ，数，数都不能分解成若干个连续的自然数之积。都不能分解成若干个连续的自然数之积。3410kkfn（ n,k)=

43、2n例例14 设设r是正奇数，证明：对任意的是正奇数，证明：对任意的正整数正整数n，有，有2n123rrrrn12,kddd例例15 设设A = 是是n的所有约数的集合，则的所有约数的集合，则B = 也是也是n的所有约的所有约数的集合。数的集合。 12,knnnddd例例16 以以d(n)表示表示n的正约数的个数，的正约数的个数， 例如：例如： d(1) = 1，d(2) = 2，d(3) = 2， d(4) = 3， 。 问：问：d(1) d(2) d(1997)是否为偶数？是否为偶数？ 例例17 设凸设凸2n边形边形M的顶点是的顶点是 ，点点O在在M的内部，用的内部，用1, 2, , 2n

44、将将M的的2n条边分别条边分别编号，又将编号，又将 也同样进行编号，也同样进行编号，若把这些编号作为相应的线段的长度，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形证明：无论怎么编号，都不能使得三角形 的周长都相等。的周长都相等。 122,nA AA122,nO AO AO A122321,nOA A OA AOA A 第二节第二节 带余除法带余除法第二节 带余除法可以看出：b整除a的充要条件是 r=0。,00( )( )a bbqrabqrrbqrqrab定理若是两个整数，其中，则存在着两个整数及 ，使得，成立，而且 及 是唯一的。式中的 及 分别叫 被 除所得的不完

45、全商和余数。l设设a a，b b是两个整数，其中是两个整数，其中b0.b0.则存在唯一的整数则存在唯一的整数q q，r r使得使得a=bq+ra=bq+r，0rb.0rb. 证明证明（存在性）考虑一个整数序列（存在性）考虑一个整数序列 ，-3b-3b，-2b-2b，-b-b，0 0，b b，2b2b，3b3b，它们将实数轴分成长度为它们将实数轴分成长度为b b的区间，而的区间，而a a必定落在其中的必定落在其中的一个区间中，因此存在一个整数一个区间中，因此存在一个整数q q使得使得 qba(q+1)bqba(q+1)b我们令我们令r=a-bqr=a-bq，则有，则有a=bq+ra=bq+r，0

46、rb0rb( (唯一性唯一性) ) 如果分别有整数如果分别有整数q q，r r和和q q1 1，r r1 1满足（满足（2 2），），则则 a= bq+ra= bq+r， 0rb0rb， a= bqa= bq1 1+r+r1 1，0r0r1 1bb两式相减，我们有两式相减，我们有 b(q-qb(q-q1 1) =-(r-r) =-(r-r1 1) )当当qqqq1 1左边的绝对值大于等于左边的绝对值大于等于b b，而右边的绝对值，而右边的绝对值小于小于b b，这是不可能的，这是不可能的. .故故q=qq=q1 1，r=rr=r1 1. .例例1 1 利用带余数除法，由利用带余数除法，由a, b

47、的值求的值求q, r .(1)14,3ab1434 (2 ),余余4,2qr(2)14,3ab 1435 (1 ), 余余5,1qr (3)14,3ab 14( 3)143 ,a qb r注注：一一般般地地，要要求求是是整整数数，是是非非负负整整数数；如果允许如果允许b取负值，则要求取负值，则要求 0.rb思考思考2861434 (2)余余正确吗？正确吗？,00a bbqrabqrrbqr带余数除法的第二种表示定理若是两个整数，其中，则存在着两个整数及 ，使得，成立，而且 及 是唯一的。,00,qZaq brab qrbbqq r证 明 分 析 ： 作 整 数 序 列， -3 b ,-2 b

48、,- b ,0, b ,2 b ,3 b ,则 a必 满 足 q ba 2，则，则 。 21 | 2 +1ba第四节第四节 辗转相除法辗转相除法定义定义 下面的一组带余数除法，称为辗转相除法。下面的一组带余数除法，称为辗转相除法。12221 0 brqrrr，111 0 babqrr，1 1 1 1 0 kkkkkkrr qrrr，,0a bb 设是整数，依次做带余数除法211 0 nnnnnnrrqrrr，1 111+0nnnnnrr qrr,。1,( , )nna ba brr定理若是任意两个正整数，则，是上式中最后一个不等于零的余数。1,( , )a ba b推论的公因数与的因数相同。例

49、例1 1 求下面各组数的最大公因数。求下面各组数的最大公因数。(1)1859,1573;ab 185915731286; 15732865143; 28614320. 解：解：(2)138,36.ab1859 15731859 1573 1 1157315732862865 5143014301431432 22862860 0( 1859,1573)143.b所所以以，(2)(138, 36)6. 注：亦可通过分解因数的方法求最大公因数注：亦可通过分解因数的方法求最大公因数. .补充说明：补充说明：利用利用1.11.1习题习题4 4的结论，可以使得辗转的结论，可以使得辗转相除法求最大公因数更

50、为快速一些。每次除得余数相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。的绝对值不超过除数的一半，余数可以为负。例例2 2 求（求（7650176501，97199719）. .76501 971976501 97198 87775277752125112518 810008100082892894 41156115695953 32852854 4242496961 14 44 40 0=1.例例3 3 利用辗转相除法计算利用辗转相除法计算 (27090, 21672, 11352). (27090, 21672, 11352). 27090 21672