本书以经典理论与现代应用相结合的方式介绍了初等数论的基本概念和技巧，其内容包括整除、同余、二次剩余、原根、指数的计算等。此外，书中包括60多位对数论有贡献的数学家的传记。
本书内容丰富，趣味性强，条理清晰，既可以作为高等院校计算机及相关专业的数论教材，也可以作为对数论和密码学感兴趣的读者的初级读物。

前　　言
　　自古（姑且说1975年以前）数论拥有数学最纯粹部分的美称.人们之所以研究数论，是因为它历史悠久且硕果累累，也因为它有大量易于理解而令人着迷的问题，更因为它富于智慧的魅力.但是前些年人们已经从新的角度来审视数论了.今天人们研究数论既出于传统的原因，又出于数论已成为密码学的基础这一引人注目的理由.本书第1版是将初等数论的现代应用与传统主题相结合的最早的教材，第5版延续了原先版本的基本思路.还没有其他的教材像本书一样以如此深思熟虑的方式介绍初等数论及其应用，使用本书的教师将会惊喜地看到现代应用是怎样天衣无缝地融入到数论课程中去的.
　　本书是为大学本科的数论课程而写的，适用于任何水平.除了一定的数学素养外，本书的大部分材料不需要什么预备知识.本书既可以作为计算机科学课程的有益补充，也可以作为有兴趣学习数论和密码学新进展的读者的初级读物.
　　第5版保持了先前版本的长处，并加以充实、改进.熟悉先前版本的教师将会乐于使用这个新版本.初次使用本书的教师则会看到这样一本最新的教材，其中将跨越几千年的数论精华与最近不到十年的新进展加以整合.熟悉先前版本的教师将会发现新版本变得更灵活且更易于教学，也更加有趣和引人入胜，他们还将发现对于数论成果的历史渊源及数论的实验方面的额外关注.
　　第5版的变化
　　应读者和审阅人的要求，新版本进行了多方面改进.新版本应该更易于教学，更易于阅读，也更有趣和令人大开眼界.新版本更有效地表达了数论的数学美和它的应用价值.值得注意的变化包括：
　　更灵活的题材组织
　　第4版的1.1节分成了较短的两节.1.1节涵盖了数和序列，并介绍丢番图逼近.1.2节涵盖了和与积.如果认为没有必要，教师可以略去这两节的大部分内容，不过很多人可能会选用关于丢番图逼近的材料.第4版的3.1节也分成了两节.3.1节介绍素数，证明素数有无穷多个，并讨论如何寻找素数.3.2节讨论素数的分布，并介绍素数定理及许多关于素数的猜想.
　　扩充了与密码学有关的内容
　　通过引进卡西斯基测试和重合次数，加进维吉尼亚密码分析，提到包括AES加密标准在内的新近的密码学进展，描述了对RSA密码系统实施攻击的方法.第12章通过使用来自用连分数的丢番图逼近的概念开发了这类攻击中的一种方法，在习题中指出了推荐的零知识证明方案的缺陷.
　最新发现
　　数论的最新发现在本书中得到了反映，其中包括一批理论上的发现以及关于证明一个整数是素数的多项式时间算法的讨论，还有关于卡塔兰猜想的结论.计算方面的发现也加进书中，例如三个新的梅森素数.本书的网站特别重视数论方面的最新结果，并提供本书出版之后新发现的种种链接.
　　新的和扩充的论题
　　1.1节介绍了丢番图逼近的内容，加入了有理数逼近实数的狄利克雷定理，给出了一个应用鸽巢原理的证明.超出初等数论范围的许多重要论题现在也得以讨论，目的是使学生对数论有一个比较全面的评价.出于类似的思考，对丢番图方程的内容作了扩充.这一版包括对比尔猜想、卡塔兰猜想及其新近分析的简要讨论，还有对费马-卡塔兰猜想的讨论.对abc猜想也作了讨论，并说明如何用它来证明一些关于丢番图方程的结果.
　　增加了关于高斯整数的新的一章.这一章介绍高斯素数、高斯整数的最大公因子、高斯整数的欧几里得算法（辗转相除法）以及高斯整数分解成高斯素数的唯一性.这新的一章还阐明怎样用高斯整数求把正整数表示为两个整数的平方和有多少方式.
　　改进了例题和证明
　　这一版给出了欧几里得关于存在无穷多素数的证明.许多关于无穷多素数的其他证明可在习题中找到.很多证明作了改进，其中包括简化或补充说明.
　　加强了习题
　　本书以其别具一格的习题而久负盛名，这一版的习题更为出色.书中全部习题已作过检查和求解；在第4版中发现的题意含糊或者条件缺失的习题得以澄清.
　　加入了几百道新的习题.补充了涉及斐波那契恒等式的习题.新增的习题用不同方法证明存在无穷多素数.新增了许多与密码学有关的习题，其中不少涉及维吉尼亚密码和RSA密码系统.在一道习题中简述了二次互反律的最新证明.还新添了更多有关非线性丢番图方程（如巴舍方程、马尔可夫方程和同余数）的习题.
　　扩充了历史渊源的叙述和人物传记
　　黎曼假设的历史和现状包含在这一版内.对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节阐述关于整数整除性的核心材料，应当采用.
　　之前所述，第3章及4.1~4.3节讲述核心材料.4.4节讨论的以素数幂为模的多项式同余方程的解法是可选的，不过对发展p进数理论是很重要的.4.5节需要一些线性代数的背景知识，这一节的材料在8.2节用到，若不需要这两节可省略.4.6节介绍一种特殊的因子分解方法（波拉德ρ方法），也可省略.
　　第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.4节讨论佩尔方程的解及用连分数求解，这两节是可选的.
　　第14章是可选的，这一章包括高斯整数.这种数的许多与整数相似的性质在这一章阐述.特别是，引入高斯素数和证明高斯整数分解的唯一性.最后，使用高斯整数可得到把一个正整数表示为两个整数平方和的方式的数目.
　　下图表示各章之间的依赖关系，用于帮助教师规划课程.虽然第2章在不需要时可省略，但其中清楚说明了描述算法复杂性的贯穿全书的大O符号.除了定理12.4依赖于第9章的材料外，第12章只依赖于第1章.在第13章中只有13.4节依赖于第12章.如果9.1节中有关原根的可选注释被略去，则可以采用第11章而不采用第9章.14.3节可以与13.3节一同采用.
　　　　
　　致谢
　　我要对我在AT&T实验室的管理同仁表示感谢，他们对这一版的准备工作给予了大力支持，并提供了一种富于激励性的专业环境.特别要感谢Bart Goddard，他为本书准备了辅助材料，并要特别感谢Douglas Eubert、Tom Wegleitner和Steve Whalen，他们协助审阅手稿以保证正确性，并对习题求解提供帮助以及反复核对习题的答案.
　　感谢本版编辑Bill Hoffman的支持，感谢本书前几版的Addison-Wesley公司的编辑们，特别需要提到Wayne Yuhasz和Jeff Pepper，他们对本书的初始思想深表赞同并认识到本书的潜在魅力，而在当时其他出版商都认为数论已是一门失去生命力的课程，毫无出版新书的价值.我还要感谢本书幕后的整个编辑、印制、营销和媒体团队，他们是：Mary Reynolds、Julie LaChance、Jeffrey Holcomb、Barbara Atkinson、Beth Anderson、Barbara Pendergast、Paul Anagnostopoulos、Emily Portwood、Lynne Blaszak、Greg Tobin和Phyllis Hubbard.我同样对David Wright表示感谢，他对本书网站作出多方面的贡献，包括有关PARI/GP的材料、数论和密码学的应用小程序以及推荐的作业.
　　我从本书前几版读者的深思熟虑的评论和建议中受益匪浅，他们的许多思想已体现在这一版中.
　　我对下列审阅人在本版的准备过程中提供的帮助深表谢意：
　　Joel Cohen,马里兰大学
　　Michael Cullinane,Keene州立大学
　　Mark Dickinson,密歇根大学
　　Kerry Jones,保尔州立大学
　　Slawomir Klimek,印第安纳大学-普度大　　　学印第安纳波利斯分校
　　Stephen Kudla,马里兰大学
　　Jennifer McNulty,蒙大拿大学
　　Stephen Miller,拉特格大学
　　Michael Mossinghoff,Davidson学院
　　Michael E.OS ullivan,圣迭戈州立大学
　　Gary Towsley,纽约州立大学Geneseo分校
　　David Wright,俄克拉何马州立大学
　　我还要再次感谢本书前几版的审阅人，他们帮助一版一版地改进本书，对他们一次又一次参与本书的审阅我会铭记在心.他们是：
　　David Bressoud,宾夕法尼亚州立大学
　　Sydney Bulman-Fleming,Wilfred Laurier大学
　　Richard Bumby,拉特格大学
　　Charles Cook,南卡罗来纳大学Sumter分校
　　Christopher Cotter,北科罗拉多大学
　　Euda Dean,Tarleton州立大学
　　Daniel Drucker,韦恩州立大学
　　Bob Gold,俄亥俄州立大学
　　Fernando Gouvea,库尔比学院
　　Jennifer Johnson,犹他大学
　　Roy Jordan,Monmouth学院
　　Herbert Kasube,布拉德雷大学
　　Neil Koblitz,华盛顿大学
　　Steven Leonhardi,Winona州立大学
　　Charles Lewis,Monmouth学院
　　James McKay,奥克兰大学
　　John Mairhuber,Maine-Orono大学
　　Alexsandrs Mihailovs,宾夕法尼亚大学
　　Rudolf Najar,加州州立大学Fresno分校
　　Carl Pomerance,乔治亚大学
　　Sinai Robins,神学院
　　Tom Shemanske,达特茅斯学院
　　Leslie Vaaler,得克萨斯大学奥斯汀分校
　　Evelyn Bender Vaskas,克拉克大学
　　Samuel Wagstaff,普度大学
　　Edward Wang,Wilfred Laurier大学
　　Betsey Whitman,Framingham州立大学
　　David Wright,俄克拉何马州立大学
　　Paul Zwier,卡尔文学院
　　最后，我要提前感谢未来对我提出建议和更正意见的诸位.您可把这样的材料按照Addison-Wesley的电子邮件地址math@awl.com发送给我.
　　

Kenneth H.Rosen
于新泽西州米德尔顿

何谓数论1
第1章　整数3
　1.1　数和序列3
　1.2　和与积11
　1.3　数学归纳法16
　1.4　斐波那契数21
　1.5　整除性27
第2章　整数的表示法和运算31
　2.1　整数的表示法31
　2.2　整数的计算机运算38
　2.3　整数运算的复杂度43
第3章　素数和最大公因子49
　3.1　素数49
　3.2　素数的分布56
　3.3　最大公因子66
　3.4　欧几里得算法71
　3.5　算术基本定理80
　3.6　因子分解法和费马数90
　3.7　线性丢番图方程98
第4章　同余104
　4.1　同余引言104
　4.2　线性同余方程112
　4.3　中国剩余定理116
　4.4　求解多项式同余方程123
　4.5　线性同余方程组127
　4.6　利用波拉德ρ方法分解整数135
第5章　同余的应用138
　5.1　整除性检验138
　5.2　万年历142
　5.3　循环赛赛程147
　5.4　散列函数148
　5.5　校验位152
第6章　特殊的同余式157
　6.1　威尔逊定理和费马小定理157
　6.2　伪素数163
　6.3　欧拉定理170
第7章　乘性函数174
　7.1　欧拉函数174
　7.2　因子和与因子个数182
　7.3　完全数和梅森素数187
　7.4　莫比乌斯反演197
第8章　密码学203
　8.1　字符密码203
　8.2　分组密码和流密码209
　8.3　取幂密码224
　8.4　公钥密码226
　8.5　背包密码233
　8.6　密码协议及应用238
第9章　原根245
　9.1　整数的阶和原根245
　9.2　素数的原根250
　9.3　原根的存在性255
　9.4　指数的算术261
　9.5　用整数的阶和原根进行素性检验269
　9.6　通用指数273
第10章　原根与整数的阶的应用278
　10.1　伪随机数278
　10.2　埃尔伽莫密码系统284
　10.3　电话线缆绞接中的一个应用288
第11章　二次剩余293
　11.1　二次剩余与二次非剩余293
　11.2　二次互反律305
　11.3　雅可比符号316
　11.4　欧拉伪素数323
　11.5　零知识证明330
第12章　十进制分数与连分数336
　12.1　十进制分数336
　12.2　有限连分数345
　12.3　无限连分数354
　12.4　循环连分数363
　12.5　用连分数进行因子分解375
第13章　某些非线性丢番图方程379
　13.1　毕达哥拉斯三元组379
　13.2　费马大定理384
　13.3　平方和394
　13.4　佩尔方程403
第14章　高斯整数409
　14.1　高斯整数和高斯素数409
　14.2　最大公因子和唯一因子分解418
　14.3　高斯整数与平方和425
附录A　整数集公理430
附录B　二项式系数432
附录C　Maple和Mathematica在数论中的
应用437
附录D　有关数论的网站444
附录E　表格446
参考文献460

数学