本书是为大学本科的数论课程而写的，适用于任何水平，除了一定的数学素养外，本书的大部分材料不需要什么预备知识，本书既可以作为计算机科学课程的有益补充，也可以作为有兴趣学习数论和密码学新进展的读者的初级读物，第7版保持了先前版本的长处，并加以充实、改进，熟悉先前版本的教师将会乐于使用这个新版本，初次使用本书的教师则会看到这样一本新的教材，其中将跨越几千年的数论精华与新近不到十年的新进展加以整合，熟悉先前版本的教师将会发现新版本变得更灵活且更易于教学，也更加有趣和引人人胜，他们还将发现对于数论成果的历史渊源及数论的实验方面的额外关注。

肯尼思·H.罗森（Kenneth H.Rosen）密歇根大学安娜堡分校数学学士，麻省理工学院数学博士。他曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学，教授离散数学、算法设计和计算机安全方面的课程；他还曾加盟贝尔实验室，并且是 AT&T 贝尔实验室的杰出技术人员。

他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言，在全球数百所大学中广为采用。

目　　录<br />何谓数论　1<br />第1章　整数　5<br />1.1　数和序列　5<br />1.2　和与积　17<br />1.3　数学归纳法　24<br />1.4　斐波那契数　31<br />1.5　整除性　39<br />第2章　整数的表示法和运算　47<br />2.1　整数的表示法　47<br />2.2　整数的计算机运算　57<br />2.3　整数运算的复杂度　64<br />第3章　最大公因子　71<br />3.1　最大公因子及其性质　71<br />3.2　欧几里得算法　80<br />3.3　线性丢番图方程　90<br />第4章　素数　99<br />4.1　素数概述　99<br />4.2　素数的分布　111<br />4.3　算术基本定理　129<br />4.4　因子分解方法和费马数　144<br />第5章　同余　155<br />5.1　同余概述　155<br />5.2　线性同余方程　168<br />5.3　中国剩余定理　173<br />5.4　求解多项式同余方程　182<br />5.5　线性同余方程组　189<br />5.6　利用波拉德ρ方法分解整数　198<br />第6章　同余的应用　203<br />6.1　整除性检验　203<br />6.2　万年历　209<br />6.3　循环赛赛程　214<br />6.4　散列函数　216<br />6.5　校验位　220<br />第7章　特殊的同余式　229<br />7.1　威尔逊定理和费马小定理　229<br />7.2　伪素数　238<br />7.3　欧拉定理　248<br />第8章　算术函数　253<br />8.1　欧拉φ函数　253<br />8.2　因子和与因子个数　265<br />8.3　完全数和梅森素数　271<br />8.4　莫比乌斯反演　288<br />8.5　拆分　296<br />第9章　密码学　313<br />9.1　字符密码　313<br />9.2　分组密码和流密码　322<br />9.3　指数密码　340<br />9.4　公钥密码学　343<br />9.5　密码协议及应用　353<br />第10章　原根　365<br />10.1　整数的阶和原根　365<br />10.2　素数的原根　373<br />10.3　原根的存在性　379<br />10.4　离散对数和指数的算术　388<br />10.5　用整数的阶和原根进行<br />　素性检验　400<br />10.6　通用指数　407<br />第11章　整数的阶的应用　413<br />11.1　伪随机数　413<br />11.2　埃尔伽莫密码系统　423<br />11.3　电话线缆绞接中的一个应用　429<br />第12章　二次剩余　437<br />12.1　二次剩余与二次非剩余　438<br />12.2　二次互反律　454<br />12.3　雅可比符号　466<br />12.4　欧拉伪素数　476<br />12.5　零知识证明　485<br />第13章　十进制分数与连分数　493<br />13.1　十进制分数　493<br />13.2　有限连分数　506<br />13.3　无限连分数　515<br />13.4　循环连分数　528<br />13.5　用连分数进行因子分解　543<br />第14章　非线性丢番图方程与<br />　椭圆曲线　547<br />14.1　毕达哥拉斯三元组　548<br />14.2　费马大定理　556<br />14.3　平方和　572<br />14.4　佩尔方程　584<br />14.5　同余数和椭圆曲线　591<br />14.6　模素数椭圆曲线　608<br />14.7　椭圆曲线的应用　617<br />第15章　高斯整数　625<br />15.1　高斯整数和高斯素数　625<br />15.2　最大公因子和唯一因子分解　636<br />15.3　高斯整数与平方和　647<br />附录A　整数集公理　653<br />附录B　二项式系数　657<br />附录C　Maple、Mathematica和SageMath<br />　在数论中的应用　665<br />C.1　Maple在数论中的应用　665<br />C.2　Mathematica在数论中的应用　670<br />C.3　SageMath在数论中的应用　677<br />附录D　有关数论的网站　683<br />附录E　表　685<br />附录F　未解决问题精选　701<br />参考文献　705<br /><br /><br />Contents<br /><br />What Is Number Theory? 1<br />1 The Integers 5<br />1.1 Numbers and Sequences 5<br />1.2 Sums and Products 17<br />1.3 Mathematical Induction 24<br />1.4 The Fibonacci Numbers 31<br />1.5 Divisibility 39<br />2 Integer Representations and Operations<br />2.1 Representations of Integers 47<br />2.2 Computer Operations with Integers 57<br />2.3 Complexity of Integer Operations 64<br />3 Greatest Common Divisors 71<br />3.1 Greatest Common Divisors and Their Properties 71<br />3.2 The Euclidean Algorithm 80<br />3.3 Linear Diophantine Equations 90<br />4 Prime Numbers 99<br />4.1 Prime Numbers 99<br />4.2 The Distribution of Primes 111<br />4.3 The Fundamental Theorem of Arithmetic 129<br />4.4 Factorization Methods and the Fermat Numbers 144<br />5 Congruences 155<br />5.1 Introduction to Congruences 155<br />5.2 Linear Congruences 168 <br />5.3 The Chinese Remainder Theorem 173<br />5.4 Polynomial Congruences 182<br />5.5 Systems of Linear Congruences 189<br />5.6 Factoring Using the Pollard Rho Method 198<br />6 Applications of Congruences 203<br />6.1 Divisibility Tests 203<br />6.2 The Perpetual Calendar 209<br />6.3 Round-Robin Tournaments 214<br />6.4 Hashing Functions 216<br />6.5 Check Digits 220<br />7 Some Special Congruences 229<br />7.1 Wilson‘s Theorem and Fermat’s Little Theorem 229 <br />7.2 Pseudoprimes 238 <br />7.3 Euler’s Theorem 248<br />8 Arithmetic Functions 253<br />8.1 The Euler Phi-Function 253<br />8.2 The Sum and Number of Divisors 265<br />8.3 Perfect Numbers and Mersenne Primes 271<br />8.4 Mobius Inversion 288<br />8.5 Partitions 296<br />9 Cryptology 313<br />9.1 Character Ciphers 313<br />9.2 Block and Stream Ciphers 322<br />9.3 Exponentiation Ciphers 340<br />9.4 Public Key Cryptography 343<br />9.5 Cryptographic Protocols and Applications 353<br />10 Primitive Roots 365<br />10.1 The Order of an Integer and Primitive Roots 365<br />10.2 Primitive Roots for Primes 373<br />10.3 The Existence of Primitive Roots 379<br />10.4 Discrete Logarithms and Index Arithmetic 388 <br />10.5 Primality Tests Using Orders of Integers and Primitive Roots 400<br />10.6 Universal Exponents 407<br />11 Applications of the Order of an Integer 413<br />11.1 Pseudorandom Numbers 413<br />11.2 The ElGamal Cryptosystem 423<br />11.3 An Application to the Splicing of Telephone Cables 429<br />12 Quadratic Residues 437<br />12.1 Quadratic Residues and Nonresidues 438<br />12.2 The Law of Quadratic Reciprocity 454<br />12.3 The Jacobi Symbol 466<br />12.4 Euler Pseudoprimes 476<br />12.5 Zero-Knowledge Proofs 485<br />13 Decimal Fractions and Continued Fractions<br />13.1 Decimal Fractions 493<br />13.2 Finite Continued Fractions 506<br />13.3 Infinite Continued Fractions 515<br />13.4 Periodic Continued Fractions 528<br />13.5 Factoring Using Continued Fractions 543<br />14 Nonlinear Diophantine Equations and Elliptic Curves 547<br />14.1 Pythagorean Triples 548<br />14.2 Fermat’s Last Theorem 556<br />14.3 Sums of Squares 572<br />14.4 Pell’s Equation 584<br />14.5 Congruent Numbers and Elliptic Curves 591<br />14.6 Elliptic Curves Modulo Primes 608<br />14.7 Applications of Elliptic Curves 617<br />15 The Gaussian Integers 625<br />15.1 Gaussian Integers and Gaussian Primes 625<br />15.2 Greatest Common Divisors and Unique Factorization 636<br />15.3 Gaussian Integers and Sums of Squares 647?<br />Appendix A Axioms for the Set of Integers 653<br />Appendix B Binomial Coefficients 657<br />Appendix C Using Maple, Mathe-matica, and SageMath for Number Theory 665<br />C.1 Using Maple for Number Theory 665 <br />C.2 Using Mathematica for Number Theory 670 <br />C.3 Using SageMath for Number Theory 677<br />Appendix D Number Theory Web Links 683<br />Appendix E Tables 685<br />Appendix F Inventory of Unsolved Problems 701 <br />Bibliography 705<br />