初等数论及其应用(原书第5版)

. 3.7　线性丢番图方程
第4章 同余
　4.1　同余引言
　4.2　线性同余方程
　4.3　中国剩余定理
　4.4　求解多项式同余方程
　4.5　线性同余方程组
　4.6　利用波拉德方法分解整数
第5章 同余的应用
　5.1　整除性检验
　5.2　万年历
5.3　循环赛赛程
5.4　散列函数
5.5　校验位
第6章 特殊的同余式
6.1　威尔逊定理和费马小定理
6.2　伪素数
6.3　欧拉定理
第7章 乘性函数
7.1　欧拉函数
7.2　因子和与因子个数
7.3　完全数和梅森素数
7.4　莫比乌斯反演
第8章 密码学
8.1　字符密码
8.2　分组密码和流密码
8.3　取幂密码
8.4　公钥密码
8.5　背包密码
8.6　密码协议及应用
第9章 原根
9.1　整数的阶和原根
9.2　素数的原根
9.3　原根的存在性
9.4　指数的算术
9.5　用整数的阶和原根进行素性检验
9.6　通用指数
第10章 原根与整数的阶的应用
　10.1　伪随机数
　10.2　埃尔伽莫密码系统
　10.3 电话线缆绞接中的一个应用
第11章 二次剩余
　11.1　二次剩余与二次非剩余
……
第12章　十进制分数与连分数
第13章　某些非线性丢番图方程
第14章　高斯整数
附录
参考文献

.　　黎曼假设的历史和现状包含在这一版内．对Skewes常数作了介绍，这是在一个数学证明中出现的最大数字之一．增加了关于Thomas Nicely发现奔腾芯片著名的除法缺陷的报道，这一发现是由于涉及孪生素数的两次计算不一致而引起的．这一版增加了很多新的人物传记，包括伯特兰、费瑞、华林、巴舍、克罗内克、莱维本热尔松和卡塔兰等．人物传记中添加了照片．
　　·对数学软件Maple和Mathematica的辅助读物和支持
　　用高斯整数进行计算的指令已增添到附录中，在这个附录中描述了用数学软件Maple和Mathematica进行数论计算的指令．
　　·对正确性的格外关注
　　这一版得益于为确保教材的正文、习题和解答的正确性而格外进行的工作，三位精心的校对费时多日以使本书尽可能避免差错．
　　·扩充了网站内容
　　本书的网站(www．awlonline．com／rosen)通过多种重要途径加以扩充和增强．“数论新闻”是一个特别关注数论新近发现的新专栏．与本书相关的包罗甚广的数论网站表已得到扩充，所有链接都已更新．这些链接将在这一版的生存期内定期更新．该网站现在还支持收罗广泛的数论与密码学的应用小程序集，这些小程序可用于相关计算和探索，该网站也支持关于PARI／GP的辅导，PARI／GP是一个用于快速数论计算的计算系统，这些应用小程序建立在这个系统之上．推荐用于学生小组或个人的题目库也可在该网站找到．
　　本书特色
　　·经典数论的发展
　　本书的核心是以一种有助于理解和引人入胜的方式阐述经典初等数论，关键结果的史料和重要性得到记述．在精心开展每个论题的基本材料之后，接着论述同一论题更复杂的结果．
　　·突出应用
　　本书的主要长处是包括了数论的种种应用．一旦需要的理论得以建立，应用就以灵活的方式编入教材．应用设计成有助于促进理论的扩展和阐明初等数论在不同方面的用处．数论广泛应用于密码学，经典密码、分组密码及序列密码、公钥密码系统和密码协议都被包括在内．对计算机科学的其他应用包括整数的快速乘法、伪随机数及校验数字．对于许多其他领域的应用，例如调度、电话、昆虫学和动物学，也可在教材中找到．
　　·一体化的论题
　　取自初等数论的很多概念都被用于素性测试和因数分解．进而，素性测试和因数分解又在数论对于密码学的应用中起着关键作用．正是如此，这些主题作为一体化的论题而被反复论述．几乎每一章都包括涉及这些主题的材料．
　　·易于入门
　　本书被设计成只需最低限度的预备知识．本书几乎是完全自足的，只需具备通常称为“大学代数”的知识．只有几处用到了一些微积分的概念(例如讨论素数分布及大O符号)，少数几处用到离散数学及线性代数的概念．所有依赖于高出大学代数论题的内容都明确注明并且都是可选的．
　　·准确性
　　已付出极大的努力以保证这一版的准确性．来自本书第4版的许多读者、审阅人及校对的意见帮助我们实现了这一目标．
　　·收入习题广博
　　学习数学的最佳途径(也许是唯一途径)就是做习题．本教材包括极为广泛和多种多样的习题．收入许多常规习题是为了训练基本技能，已注意将带有奇数编号的和偶数编号的两种习题包含在这一类题中．大量中等难度的题有助于学生把若干概念结合起来形成新的结果．许多其他习题或习题组则是为发展新概念而设计的．具有挑战性的习题也是充足的，用单星号(*)表示难题，双星号(**)表示很难的题．有些题包含以后正文中要用到的结果，这些题用手指符号()表示．这样的习题教师在适当的时候应尽可能布置．
　　提供了广泛的上机作业．每一节都包括借助于数学软件Maple、Mathematica或由学生或教师自编的计算程序可以完成的计算和探索问题．这类常规的习题可使学生学会如何应用Maple或Mathematica的基本指令(在附录D中描述)，而更多开放性的问题是为实验及激发创造性而设计的．每节还包括一批编程作业，要由学生使用自己选择的程序设计语言来完成，可以用Maple和Mathematica中的语言，也可以用另外的语言．..
　　·习题答案
　　奇数编号的习题答案从本书网站下载．
　　·以经验为依据的发现
　　在本书的许多地方，考察数值凭据有助于促使关键结果的产生．这种做法使学生有机会运用猜想，这正如当初人们在获得许多数论结果所做的那样．
　　·广泛的例题
　　本书包括阐明每个重要概念的例题．这些例题是为阐明书中的定义、算法和证明而设计的．这些例题也用以帮助学生完成每节之后的习题．
　　·注意诱导式的证明
　　书中的许多证明用例题作为诱导，在正式证明和说明证明的关键思想之前先用例题作为诱导．证明本身则以仔细、严谨和完全明白的方式表述．证明的设计使学生对每一步和整个推理过程都能理解．经常在正式证明之前给出说明证明步骤的数值例题．
　　·关于算法的推导
　　有关初等数论算法的方方面面贯穿本书始终．不仅描述算法，而且对其复杂性加以分析．在本书描述的算法中，有多种计算最大公约数、素性测试和因数分解的算法．本书包含算法复杂性的讨论，教师在自己的课程中可以随意取舍．
　　·人物传记和历史注释
　　这一版包括60多位对数论有贡献的数学家的传记．这些有贡献的人包括古代的、中世纪的、16至18世纪的、19世纪的和20世纪的，既有东方的，也有西方的．编写这些传记是为了让学生们对这些有卓越贡献的人作出正确的评价，他们往往引领了(甚至仍然引领着)有趣的研究方向．
　　·未解决的问题
　　数论中未解决的问题在书中随处可见，有些在正文中，另一些则在习题中．这些问题表明数论是一门仍在向前发展的学科．读者应当认识到试图解决这些难题往往可能耗费大量时日而徒劳无功．然而，如果其中某些问题在未来几年仍得不到解决，人们还是会感到惊奇．
　　·最新的内容
　　书中包括数论的最新发现．描述了许多未解决问题的现状，例如新的理论成果．2004年9月关于素数和因数分解的新发现已列入这一版的第一次印刷之中．这些发现将有助于读者理解数论是一个极为活跃的研究领域．他们可以看到甚至他们自己有可能参与发现新的素数．
　　·参考文献
　　本书提供了内容广泛的参考文献目录．这个目录列出主要的已出版的数论资源，包括书籍和论文．开列了很多有用的教材，诸如论述数论史的著作和数论方方面面的专著．包含许多原始文献，例如有关密码学的资料．
　　·数学软件Maple和Mathematica的支持
　　本书提供了一个附录，其中列出Maple 和Mathematica用于数论计算的命令．这些命令是按照有关章节中的内容列出的．
　　·网络资源
　　本书的网站(www．awlonline．com／rosen)包括与本书相关的数论内容以及一大批其他资源．为了方便起见，最重要的数论网站都在附录D中列出．
　　·表格
　　附录E包含帮助学生进行计算和实验的5个表格，查看这些表格能帮助学生探寻建立相关模式及公式的猜想．当这些表格不够用时，建议使用诸如数学软件Maple和Mathematica这样的计算软件包．
　　·符号表
　　本书使用的符号表及对应定义的页码列于文前．
　　辅助材料
　　·网站
　　本书网站包含一大批与数论有关的网站的指南，提供带有注释的链接．这些网站与书中进行相关材料讨论的页面联系在一起，网站还包括显示数论方面最新发现的部分，同时也提供广泛的数论和密码学的应用小程序．
　　如何使用本书
　　本书的设计极其灵活．对于一门数论课程，基本的核心材料可以包括：讨论整数的整除性的1．5节，讨论素数、因子分解与最大公因子的第3章，讨论同余的4．1～4．3节，介绍包含费马小定理的重要同余式的第6章．教师可选择其他内容对核心材料加以补充来设计自己的课程．为了帮助教师选择课程所包含的章节，将本书的不同部分概述如下：
　　1．1～1．4节的材料是可选的．1．1节介绍整数的不同类型、整数序列与可数性，还介绍丢番图逼近的概念．1．2节可帮助有需求的学生复习和与积．1．3节介绍数学归纳法，这些内容学生可能已在别处学习过了．(关于整数公理与二项式定理的材料可在附录中找到．)1．4节介绍斐波那契数，这是许多教师喜爱的论题，学生可能在离散数学的课程中学过．如前所述，1．5节阐述关于整数整除性的核心材料，应当采用．
　　第2章是可选的，包括以6为基的整数表示、整数的计算机运算与整数运算的复杂性．2．3节引入大O符号．对于以前还未在别处见过这个符号的学生，这是很重要的，尤其是当教师要着重讲述数论中的计算复杂性时．
　　如前所述，第3章及4．1～4．3节讲述核心材料．4．4节讨论的以素数幂为模的多项式同余方程的解法是可选的，不过对发展卢进数理论是很重要的．4．5节需要一些线性代数的背景知识，这一节的材料在8．2节用到，若不需要这两节可省略．4．6节介绍一种特殊的因子分解方法(波拉德p方法)，也可省略．
　　第5章是可选的．教师可从数论的不同应用中选讲一些．5．1节介绍整除性检验；5．2节涉及万年历；5．3节讨论循环赛赛程安排；5．4节说明怎样将同余式用于散列函数；5．5节描述如何寻找和使用校验位．正如前面提到的，第6章讲述核心材料．
　　第7章讨论乘性函数．7．1节应予采用，介绍乘性函数的基本概念并研究欧拉φ函数．因子和及因子个数的函数在7．2节讨论，这一节推荐所有教师采用．所有教师大概都会采用7．3节，这一节介绍完全数的概念并描述如何寻找梅森素数．
　　第8章包括数论在密码学中的应用．竭力推荐这一论题，因为这很重要，并且学生也会发现它极为有趣．8．1节介绍这个主题的基本术语以及一些经典的字符密码，计划在课程中包括密码学内容的教师务必要采用这一节．8．2节介绍分组与流密码，这是两类重要的密码，并且给出这两类密码基于数论的例子．8．3节包括基于模取幂运算的特殊类型的分组密码．8．4节应为所有的教师采用，这一节介绍公钥密码的基本概念，并用RSA密码系统加以说明．8．5节讨论背包密码，这一节是可选的．8．6节提供关于密码协议的导引，向对现代密码学的应用感兴趣的教师竭力推荐这一节．(密码学的其他论题包含在第9～11章内．)
　　第9章涉及整数的阶、原根及指数的算术等概念．9．1～9．4节在可能的情况下应予采用．9．5节讨论如何将这一章的概念用于素性检验，并论述费马小定理的部分逆命题．9．6节讨论通用指数，是可选的，这一节包括一些关于卡迈克尔数的有趣结果．
　　第10章介绍一些使用第9章材料的应用．这一章包括讨论伪随机数、埃尔伽莫密码系统以及电话线缆绞接方案的三节，这些材料是可选的．强调密码学应用的教师会特别愿意采用10．2节．
　　11．1节及11．2节讨论二次剩余及二次互反律，这是数论的一个主要结果，只要可能就应采用．11．3节及11．4节讨论雅可比符号与欧拉伪素数，是可选的．11．5节包括零知识证明，对密码学感兴趣的教师只要有可能就会采用这一节．
　　12．1节包括十进制分数，会被很多教师所采用．对连分数有兴趣的教师会采用12．2～12．4节，这几节建立了关于有限连分数与循环连分数的基本结果．12．5节讨论用连分数进行因子分解，是可选的．
　　大部分教师会采用13．1节及13．2节，这两节分别讨论毕达哥拉斯三元组及费马大定理．13．3节讨论平方和，13．斗节讨论佩尔方程的解及用连分数求解，这两节是可选的．第14章是可选的，这一章包括高斯整数．这种数的许多与整数相似的性质在这一章阐述．特别是，引入高斯素数和证明高斯整数分解的唯一性．最后，使用高斯整数可得到把一个正整数表示为两个整数平方和的方式的数目．
　　下图表示各章之间的依赖关系，用于帮助教师规划课程．虽然第2章在不需要时可省略，但其中清楚说明了描述算法复杂性的贯穿全书的大O符号．除了定理12．4依赖于第9章的材料外，第12章只依赖于第1章．在第13章中只有13．4节依赖于第12章．如果9．1节中有关原根的可选注释被略去，则可以采用第11章而不采用第9章．14．3节可以与13．3节一同采用．...
　　Kenneth H．Rosen
　　于新泽西州米德尔顿