本书以经典理论与现代应用相结合的方式介绍了初等数论的基本概念和方法，内容包括整除、同余、二次剩余、原根以及整数的阶的讨论和计算。此外，书中附有60多位对数论有贡献的数学家小传记。本书内容丰富，趣味性强，条理清晰，既可以作为高等院校计算机及相关专业的数论教材，也可以作为对数论和密码学感兴趣的读者的初级读物。
前 言
我最初编写本书的目的是写一本关于数论的入门级读物.起初我的想法是制作一个教学上的有效工具.我希望能展示这一数学分支中丰富的题材以及出乎意料的实用性.数论既是古典的又是现代的，既是理论的又是实用的.在本书中我力求抓住数论的这些对立面，并最大限度地将它们糅合在一起.在本书的历次修订中我维持了这些想法，并努力深化最初的想法，同时添加了一些新发现和应用.
本书是本科阶段数论课程的理想教材.除一些必要的数学素养和大学代数知识外不需要其他预备知识.本书也可作为初等数论参考资料：既可以作为计算机科学课程的有益补充，也可以作为对数论和密码学新进展感兴趣的读者的初级读物.因为本书内容全面，所以可以作为教材，也可以作为学习初等数论及其广泛应用的长期参考书.
自本书第1版出版以来，数论中的许多重要猜想得到了解决.计算机运算能力的提升导致了一系列惊人的发现.在过去的40年里，数论出现了许多新应用，包括在密码学中的许多应用.每一次修订新版，我都力求涵盖一些新主题，使本书与时俱进.
该版本的发行是为了庆祝本书出版38周年.多年来，全世界有超过10万名学生使用本书的各个版本学习数论.本书各版本都受益于许多师生和审阅者的反馈和建议.这个新版本延续了前几版的基本框架，但有许多改进和补充.希望不熟悉本书的教师，或者没有读过最近几个版本的读者，仔细通读第7版.你们会欣赏到本书中丰富的习题、引人入胜的人物传记和历史注记、最新进展的追踪、严谨的证明、有用的例子、丰富的应用、对数学软件（Maple、Mathematica和SageMath）的支持，以及大量网络资源.
第7版的变化
第7版的改动是为了使本书更易于教学、更有趣味性，并且尽可能及时更新诸多进展.许多改动是由第6版的读者和审阅者提出的.下面列出本版的一些重要更改.
●多样性、公平性和包容性
我们努力使新版更加充分地支持多样性、公平性和包容性.出版社对本书进行了全面审查.由于这次审查而做的改动包括新的和改进的人物传记以及习题的修订.
●新发现
本版追踪了数值计算和理论证明方面的新发现.在数值计算方面的新发现给出了四个新的梅森素数、新的已知的最大孪生素数，以及支持许多重要猜想的证据等.新的理论发现贯穿全书，比如弱哥德巴赫猜想的证明和存在使用O(nlog2n)次位运算来计算两个n位整数的乘积的算法等结果.
●人物传记和历史注记
包括陈景润、Derrick Lehmer和Sophie Germain在内的许多传记都进行了较大修改.补充了许多传记，尤其是在世和近代数学家的传记，包括Manindra Agrawal、Emma Lehmer、Craig Gentry、Dan Shanks、John von Neumann、Lenore Blum、Taher ElGamal、Preda V.Mihǎilescu、Helmut Hasse和Hendrik Willem Lenstra Jr.
●开放问题
如前所述，自本书第1版出版以来，数论中许多悬而未决的问题得到了解决.尽管如此，数论仍然有大量易于理解但未解决的问题.本版提供了大量开放问题，其中许多可以在附录F中找到 附录F在中文版中没有列出，有需要者可以从网址 />●更灵活的组织
第6版中关于最大公因子和素数的第3章在本版中被分为两章第3章关于最大公因子和第4章关于素数.这样更便于教师使用本书备课.
●与抽象代数的联系
虽然本书没有假定读者具备抽象代数预备知识，但介绍了一些基本的代数结构，如群、环和域.例如引入了模p的整数环，其中p是素数，还涵盖了由算术函数集上的直接加法与狄利克雷乘法运算构成的交换环狄利克雷环.这对已学过抽象代数的学生有用，也对将来要学抽象代数的学生理解其中的重要概念有益.
●密码学
扩大了密码学的覆盖范围.增加了椭圆曲线密码的内容，而背包密码的内容被删除，因为它已成为公钥密码学发展的历史脚注.引入了同态加密这一重要概念.
●原根和离散对数
判定哪些正整数具有原根的定理的证明被简化了.引入了离散对数的小步-大步算法.
●模p椭圆曲线
增加了模p椭圆曲线的内容，其中p是奇素数，补充了实数上椭圆曲线的相关内容.增加了通过模奇素数Hendrik-Lenstra椭圆曲线方法来分解因子的内容.讨论了椭圆曲线在密码学中的应用，包括ElGamal椭圆曲线密码系统的简要介绍、椭圆曲线Diffie-Hellman密钥交换和椭圆曲线数字密钥交换.
●增强型习题集
为了改进习题，我们做了大量工作.增加了几百个新习题，从常规的到具有挑战性的都有.此外，增加了一些新的计算和研究习题.
●准确性
为了本书的准确性我们付出了不少努力.本书的每一章都由两名独立的审稿者对准确性进行审查，并且由其他人员进行全面审查.交叉引用的资料也已经过仔细检查.
习题集
习题非常重要，我将相当多的精力投入在编写和修订习题的工作上.学生应该记住，想学好数学就要尽可能地多做习题.下面简要介绍本书中的习题类型以及答案的出处.
●普通习题
普通习题着重训练基本技能，注意这种习题奇数编号和偶数编号的都有.大量中等难度的习题帮助学生融合若干概念形成新的结果，也有许多习题是为了建立新概念.教师也可以为学有余力的学生找一些具有挑战性的习题.
●有难度的习题
书中有不少具有挑战性的习题，用*标记较难的习题，用**标记极难的习题.有一些习题包含的结果后面将会用到,这些习题用标记，应尽可能完成这类习题.
●习题答案
本书的后面提供了所有奇数编号习题答案 限于篇幅，中文版中没有给出答案部分内容，有需要者可以从网址 Solutions Manual中找到.所有解答都经过了多次检查，以确保准确性.
●计算习题
每一节都包括计算和研究，这些计算和研究类习题需要用一个计算程序来完成，可用诸如Maple、Mathematica、PARI/GP或SageMath之类的软件，或者使用由教师或学生自己编写的程序.学生可以进行一些常规的计算练习来学习如何使用基本命令（如附录C中Maple、Mathematica和SageMath的命令以及PARI/GP网站上的命令），也可尝试为实验和创造力而设计的更多开放式问题.每节还包括一组编程项目，学生可以选用一种编程语言或程序来完成.
网站
教师可通过本书英文版的网站www.pearsonhighered.com/rosen7e获取专为教师提供的资源，这些资源的获取需要通过Pearson获得密码.学生和教师也可以在该网站发现许多可以与本书结合使用的资源.
●外部链接
本书的英文版网站包含一个指南，提供了许多与数论相关的网站的注释链接.附录D中列出了一些与数论相关的重要网站.
●教师手册 教师手册仅供教师使用，教师可在本书英文版网站www.pearsonhighered.com/rosen7e凭密码访问.
包含所有习题的答案，包括偶数编号习题的答案，以及很多不对学生开放的其他资源，包括教学大纲、教学建议以及试题库等.
如何使用本书设计课程
本书可以作为不同专业和不同层次的初等数论课程的教材.因此，教师可以灵活地设计教学大纲.大多数教师都想覆盖第1章（根据需要）、2.1节（根据需求）、第3章和第4章、5.1节~5.3节、第7章、8.1节~8.3节和10.1节、10.2节中的核心内容.
制定教学大纲时，教师可以添加自己感兴趣的主题.主题通常可以大致分为纯理论的和应用的.纯理论的主题包括莫比乌斯反演（8.4节）、整数拆分（8.5节）、原根（第10章）、连分数（第13章后半部分）、丢番图方程（第14章前半部分）、椭圆曲线（第14章后半部分）和高斯整数（第15章）.
一些教师希望涵盖一些易于理解的应用，例如整除性测试、万年历和校验位（第6章）.想强调计算机应用和密码学的教师应涵盖第2章和第9章，可能还应包括10.3节和10.4节、第11章以及12.5节和14.7节.
在决定涵盖哪些主题后，教师可以参考下面的各章之间的关系图：
尽管可以省略第2章，但它解释了全书描述数理论算法复杂性所使用的大O表示法.除了定理13.4依赖第10章，第13章仅依赖第1章.14.4节是第14章中唯一依赖第13章的部分.如果第12章中省略涉及10.1节中原根的注释，则可以跳过第10章来学习第12章.15.3节应与14.3节一起学习.希望介绍椭圆曲线的教师可以覆盖14.5节和14.6节，如果他们希望涉及模p椭圆曲线的应用，可以增加14.7节.
如需要进一步帮助，教师可以参考英文版网站上的教师资源指南（Instructors Resource Guide）中提供的不同课程的教学大纲建议.
致谢
感谢培生的编辑Jonathan Krebs的持续大力支持和热情，他尽心尽力，确保了本版的顺利出版.Jonathan在确保质量方面提供了很多建议.感谢Jeff Weidenaar，他是本书的原编辑，在Jonathan Krebs换了工作后他接管了相关工作.感谢编辑Bill Hoffman，他编辑这本书的时间比之前的许多编辑都要长得多.本书的制作、营销和媒体团队，包括Rajinder Singh（内容制作人）、Anjali Singh（图片研究员）、Nicholas Sweeney（媒体制片人）、培生的Stacey Sveum（高级产品营销经理）、Paul Anagnostopoulos（项目经理）、MaryEllen Oliver（文案编辑、校对），以及Windfall Software的Laurel Muller（艺术家）.
我还要再次感谢所有支持本书前六版出版工作的人，包括之前的Addison-Wesley的众多编辑以及AT&T贝尔实验室的管理层.
感谢Nathan Moyer、Michael Freeze和Will Murray的帮助，他们检查和复查了整个手稿，包括习题的答案.感谢Dan Jordan，他准备书末习题答案以及在线教师手册.Dan还校对了整本书并核对了解答习题的交叉参考资料.他在很多其他方面也对我帮助很大.
感谢Marc Renault在附录C中提供的用于数论的SageMath命令，感谢Eric Schulz在附录C中提供的Mathematica命令，以及Douglas Meade在附录C中提供的Maple命令.这些计算软件在过去十年中演变颇多.
审阅人
我从以前读者的深思熟虑的评论和建议中受益颇多，我向所有人表示衷心的感谢.他们的许多想法已被纳入本版.我非常感谢帮助审阅第7版的下列人员：
David Nacin，威廉帕特森大学
Jennifer Beineke，西新英格兰大学
Robert Gross，波士顿学院
Chris Schneider，威廉伍兹大学
Nathan Moyer，惠特沃斯大学
Will Murray，加州州立大学长滩分校
Kevin Ferland，宾州布卢姆斯堡大学
Emma Previato，波士顿大学
Jeffrey L.Meyer，雪城大学
Joel Cohen，马里兰大学
Andrew Sills，乔治亚南方大学
Mits Kobayashi，加州理工大学波莫纳分校
Alia Khurram，韦恩州立大学
Christian Roettger，爱荷华州立大学
Diane Meuser，波士顿大学
Hassan Farhat，内布拉斯加大学奥马哈分校
Michael Freeze，北卡罗来纳大学威尔明顿分校
我还要感谢前几版的50多位审阅人. 他们的工作同样有助于改进本书.
密歇根大学数学学士，麻省理工学院数学博士。曾就职于科罗拉多大学，俄亥俄州立大学，缅因大学，后加盟贝尔实验室，现为AT&T实验室特别成员。Rosen博士在数论领域与数学建模领域著有大量的论文及专著，除本书外，还著有经典作品《离散数学及其应用》 （本书中文版、影印版已由机械工业出版社引进出版）。此外，他还担任CRC出版社离散数学丛书的主编。
译者序
前言
何谓数论1
第1章 整数4
1.1 数和序列4
1.2 和与积13
1.3 数学归纳法18
1.4 斐波那契数24
1.5 整除性30
第2章 整数的表示法和运算35
2.1 整数的表示法35
2.2 整数的计算机运算42
2.3 整数运算的复杂度47
第3章 最大公因子53
3.1 最大公因子及其性质53
3.2 欧几里得算法59
3.3 线性丢番图方程67
第4章 素数74
4.1 素数概述74
4.2 素数的分布83
4.3 算术基本定理96
4.4 因子分解方法和费马数107
第5章 同余116
5.1 同余概述116
5.2 线性同余方程126
5.3 中国剩余定理129
5.4 求解多项式同余方程136
5.5 线性同余方程组141
5.6 利用波拉德方法分解整数148
第6章 同余的应用151
6.1 整除性检验151
6.2 万年历156
6.3 循环赛赛程160
6.4 散列函数161
6.5 校验位165
第7章 特殊的同余式171
7.1 威尔逊定理和费马小定理171
7.2 伪素数177
7.3 欧拉定理185
第8章 算术函数189
8.1 欧拉函数189
8.2 因子和与因子个数197
8.3 完全数和梅森素数203
8.4 莫比乌斯反演216
8.5 拆分222
第9章 密码学235
9.1 字符密码235
9.2 分组密码和流密码241
9.3 指数密码255
9.4 公钥密码学258
9.5 密码协议及应用265
第10章 原根273
10.1 整数的阶和原根273
10.2 素数的原根279
10.3 原根的存在性284
10.4 离散对数和指数的算术290
10.5 用整数的阶和原根进行素性
检验300
10.6 通用指数305
第11章 整数的阶的应用310
11.1 伪随机数310
11.2 埃尔伽莫密码系统317
11.3 电话线缆绞接中的一个
应用321
第12章 二次剩余326
12.1 二次剩余与二次非剩余326
12.2 二次互反律339
12.3 雅可比符号349
12.4 欧拉伪素数358
12.5 零知识证明365
第13章 十进制分数与连分数371
13.1 十进制分数371
13.2 有限连分数381
13.3 无限连分数389
13.4 循环连分数399
13.5 用连分数进行因子分解410
第14章 非线性丢番图方程与椭圆
曲线413
14.1 毕达哥拉斯三元组414
14.2 费马大定理420
14.3 平方和432
14.4 佩尔方程442
14.5 同余数和椭圆曲线447
14.6 模素数椭圆曲线460
14.7 椭圆曲线的应用466
第15章 高斯整数474
15.1 高斯整数和高斯素数474
15.2 最大公因子和唯一因子
分解482
15.3 高斯整数与平方和490
附录495
附录A 整数集公理495
附录B 二项式系数496
附录C Maple、Mathematica和
SageMath在数论中的
应用501
附录D 有关数论的网站514
附录E 表515
参考文献529
书单推荐
