Elementary Number Theory and Its Applications

by Rosen, Kenneth H.

• ISBN13: 9780321237071
• ISBN10: 0321237072
• Edition: 6th
• Format: Hardcover
• Copyright: 2011-01-01
• Publisher: Addison Wesley

Summary

Elementary Number Theory and Its Applicationsis noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. Computational exercises and computer projects are also provided. In addition to years of use and professor feedback, the fifth edition of this text has been thoroughly checked to ensure the quality and accuracy of the mathematical content and the exercises. The blending of classical theory with modern applications is a hallmark feature of the text. The Fifth Edition builds on this strength with new examples and exercises, additional applications and increased cryptology coverage. The author devotes a great deal of attention to making this new edition up-to-date, incorporating new results and discoveries in number theory made in the past few years.

Table of Contents

What Is Number Theory?	1	(4)
The Integers	5	(38)
Numbers and Sequences	6	(10)
Sums and Products	16	(7)
Mathematical Induction	23	(7)
The Fibonacci Numbers	30	(7)
Divisibility	37	(6)
Integer Representations and Operations	43	(24)
Representations of Integers	43	(10)
Computer Operations with Integers	53	(7)
Complexity of Integer Operations	60	(7)
Primes and Greatest Common Divisors	67	(74)
Prime Numbers	68	(9)
The Distribution of Primes	77	(13)
Greatest Common Divisors	90	(7)
The Euclidean Algorithm	97	(11)
The Fundamental Theorem of Arithmetic	108	(15)
Factorization Methods and the Fermat Numbers	123	(10)
Linear Diophantine Equations	133	(8)
Congruences	141	(48)
Introduction to Congruences	141	(12)
Linear Congruences	153	(5)
The Chinese Remainder Theorem	158	(10)
Solving Polynomial Congruences	168	(6)
Systems of Linear Congruences	174	(10)
Factoring Using the Pollard Rho Method	184	(5)
Applications of Congruences	189	(26)
Divisibility Tests	189	(6)
The Perpetual Calendar	195	(5)
Round-Robin Tournaments	200	(2)
Hashing Functions	202	(5)
Check Digits	207	(8)
Some Special Congruences	215	(24)
Wilson's Theorem and Fermat's Little Theorem	215	(8)
Pseudoprimes	223	(10)
Euler's Theorem	233	(6)
Multiplicative Functions	239	(38)
The Euler Phi-Function	239	(11)
The Sum and Number of Divisors	250	(7)
Perfect Numbers and Mersenne Primes	257	(12)
Mobius Inversion	269	(8)
Cryptology	277	(56)
Character Ciphers	278	(8)
Block and Stream Ciphers	286	(19)
Exponentiation Ciphers	305	(3)
Public Key Cryptography	308	(8)
Knapsack Ciphers	316	(7)
Cryptographic Protocols and Applications	323	(10)
Primitive Roots	333	(46)
The Order of an Integer and Primitive Roots	334	(7)
Primitive Roots for Primes	341	(6)
The Existence of Primitive Roots	347	(8)
Index Arithmetic	355	(10)
Primality Tests Using Orders of Integers and Primitive Roots	365	(7)
Universal Exponents	372	(7)
Applications of Primitive Roots and the Order of an Integer	379	(22)
Pseudorandom Numbers	379	(10)
The ElGamal Cryptosystem	389	(5)
An Application to the Splicing of Telephone Cables	394	(7)
Quadratic Residues	401	(54)
Quadratic Residues and Nonresidues	402	(15)
The Law of Quadratic Reciprocity	417	(13)
The Jacobi Symbol	430	(9)
Euler Pseudoprimes	439	(9)
Zero-Knowledge Proofs	448	(7)
Decimal Fractions and Continued Fractions	455	(54)
Decimal Fractions	455	(13)
Finite Continued Fractions	468	(10)
Infinite Continued Fractions	478	(12)
Periodic Continued Fractions	490	(14)
Factoring Using Continued Fractions	504	(5)
Some Nonlinear Diophantine Equations	509	(38)
Pythagorean Triples	510	(6)
Fermat's Last Theorem	516	(12)
Sums of Squares	528	(11)
Pell's Equation	539	(8)
The Gaussian Integers	547	(30)
Gaussian Integers and Gaussian Primes	547	(12)
Greatest Common Divisors and Unique Factorization	559	(11)
Gaussian Integers and Sums of Squares	570	(7)
A Axioms for the Set of Integers	577	(4)
B Binomial Coefficients	581	(8)
C Using Maple and Mathematica for Number Theory	589	(10)
Using Maple for Number Theory	589	(4)
Using Mathematica for Number Theory	593	(6)
D Number Theory Web Links	599	(2)
E Tables	601	(16)
Answers to Odd-Numbered Exercises	617	(72)
Bibliography	689	(14)
Index of Biographies	703	(2)
Index	705	(16)
Photo Credits	721