Elementary Number Theory and Its Applications

Kenneth H. Rosen
Publisher:
Publication Date:
2005
Number of Pages:
719
Format:
Hardcover
Edition:
5
Price:
116.00
ISBN:
0-321-23707-2
Category:
Textbook
[Reviewed by
David P. Roberts
, on
02/1/2005
]

In the first paragraph of his preface, Kenneth H. Rosen says of his own book, "No other number theory text presents elementary number theory and its applications in as thoughtful a fashion as this book does." The boastful tone remains present throughout the eleven-page preface in which poor Rosen seems almost bound by some marketing requirement to say everything twice. All this is quite unfortunate, as Rosen's book itself is written in a pleasant modest tone and is very good indeed.

The book has fourteen chapters as follows:

 1. The Integers 8. Cryptology 2. Integer Representations and Operations 9. Primitive Roots 3. Primes and Greatest Common Divisors 10. Applications of Primitive Roots... 4. Congruences 11. Quadratic Residues 5. Applications of Congruences 12. Decimal Fractions and Continued Fractions 6. Some Special Congruences 13. Some Nonlinear Diophantine Equations 7. Multiplicative Functions 14. The Gaussian Integers

The core course consists of parts of Chapters 1, 3, 4, and 6. Chapters 2, 5, 8, and 10 have either a computer science or an applied feel. Chapters 7, 9, 11, 12, 13, and 14 represent more advanced pure topics. There is a long exercise set at the end of each section, for a total of sixty-five exercise sets in all.

A mathematically strong high school student would profit from reading certain parts of the book. Towards the other extreme, I, as a professional number theorist, learned a few new number-theoretic facts in the process of reviewing the text. In the main, however, Rosen's text is aimed at upperclass undergraduates. In a one-semester course for such students, I'd say instructors should design a syllabus based on about a third of the book. The rest of the book could then serve students as an accessible reference.

On the whole, the book has the professional finished quality that one would expect of a fifth edition. However some polishing remains to be done. For example, each of the exercise sets is broken into three parts: hand exercises, easier computer exercises, and harder computer exercises. The numbering restarts with each part, so that, for example, in Section 7.1 there are three problems that one might want to label 7.1.3. The easier computer part always starts with the directive, "Using a computation program such as Maple or Mathematica, or programs you have written, carry out the following computations and explorations." The harder computer part always starts with "Write programs using Maple, Mathematica, or a language of your choice to do the following." Thus these sentences, both awkward and next to useless, are each repeated 65 times!

One place where the book really shines is in the enormous number of pedagogically appropriate hand exercises. Seventy-two pages in the back of the book give or sketch answers to the odd-numbered exercises. The first Exercise 7.1.3 offers an example of an excellent exercise, towards the easier end of Rosen's spectrum. It says simply "Show φ(5186) = φ(5187) = φ(5188)." It's intended that the student factor the three arguments using the old-fashioned smallest-prime-divisor table given in an appendix, and then apply the main result of the section, the multiplicativity of Euler's φ function. But clearly this exercise has charms which go beyond reinforcing the material. It is self-checking because the three totally independent calculations need to come out the same. It is mind-expanding because students will surely ask themselves whether (5186, 5187, 5188) is the smallest such triple and whether there are any others.

Another strong point of Rosen's book is the attention to chronology. There is a fair amount of historical narrative in the main text. Heavy attention is skillfully given to very recent work. Accompanying all this are 63 boxed mini-biographies of mathematicians mentioned in the text. I would prefer that even more historical material be intertwined with the mathematics. For example, Hand Exercise 7.3.16 gives a construction of "amicable pairs" which is complicated enough to strain the patience of most students. Inserting the fact that the construction was first discovered in the ninth century by the Arab mathematician Thabit ibn Qurra would have added interest.

Another point of Rosen's book particularly to my liking is the many computer exercises. As an improvement for future editions, I would suggest an occasional worked out example in the text. Five to ten boxes containing explicit code, set off like the historical boxes, would not change the tone of the book. As an example, the book already discusses the Lucas-Lehmer test for the Mersenne number 2p-1 to be prime, the index p being an odd prime. But students would surely have an enlarged perspective if shown that

 MersenneQ[p_] := (f[x_] := Mod[x^2-2,2^p-1]; Nest[f,4,p-2]==0)


is all that's needed for a Mathematica implementation. While this MersenneQ is hardly run-time optimized, it confirms in ten minutes that the pre-1980 largest prime record 244497-1 is indeed prime. Examples such as this one would give students a running start into the computer exercises.

I would prefer that the book emphasize more the important role of heuristic argument in number theory. As a leading example, consider the heuristic associated to the Prime Number Theorem, namely that a randomly chosen integer near a large number x has chance 1/log(x) of being prime. Rosen states this heuristic but does not pursue how it supports many of his other topics, things like the twin prime conjecture, the expectation that only finitely many of the Fermat numbers 22n+1 are prime, and the expectation that infinitely many of the Mersenne numbers 2p-1 are prime. All this would fit nicely in a section designated non-core because of its dependence on freshman calculus. Students going through this section would see number theory from a different and profound angle. They would encounter the significant philosophical questions associated with the concept of near-certainty.

The MathSciNet review of the fourth edition of Rosen's book starts with "This exemplary undergraduate number theory text keeps getting better." Certainly the fifth edition is better than the fourth. I trust there will be a sixth edition and the trend will continue.

David Roberts is associate professor of mathematics at the University of Minnesota, Morris.

BLL — The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

P. What is Number Theory?

1. The Integers.

Numbers and Sequences.

Sums and Products.

Mathematical Induction.

The Fibonacci Numbers.

2. Integer Representations and Operations.

Representations of Integers.

Computer Operations with Integers.

Complexity of Integer Operations.

3. Primes and Greatest Common Divisors.

Prime Numbers.

The Distribution of Primes.

Greatest Common Divisors.

The Euclidean Algorithm.

The Fundemental Theorem of Arithmetic.

Factorization Methods and Fermat Numbers.

Linear Diophantine Equations.

4. Congruences.

Introduction to Congruences.

Linear Congrences.

The Chinese Remainder Theorem.

Solving Polynomial Congruences.

Systems of Linear Congruences.

Factoring Using the Pollard Rho Method.

5. Applications of Congruences.

Divisibility Tests.

The perpetual Calendar.

Round Robin Tournaments.

Hashing Functions.

Check Digits.

6. Some Special Congruences.

Wilson's Theorem and Fermat's Little Theorem.

Pseudoprimes.

Euler's Theorem.

7. Multiplicative Functions.

The Euler Phi-Function.

The Sum and Number of Divisors.

Perfect Numbers and Mersenne Primes.

Mobius Inversion.

8. Cryptology.

Character Ciphers.

Block and Stream Ciphers.

Exponentiation Ciphers.

Knapsack Ciphers.

Cryptographic Protocols and Applications.

9. Primitive Roots.

The Order of an Integer and Primitive Roots.

Primitive Roots for Primes.

The Existence of Primitive Roots.

Index Arithmetic.

Primality Tests Using Orders of Integers and Primitive Roots.

Universal Exponents.

10. Applications of Primitive Roots and the Order of an Integer.

Pseudorandom Numbers.

The EIGamal Cryptosystem.

An Application to the Splicing of Telephone Cables.

Quadratic Residues and nonresidues.

The Law of Quadratic Reciprocity.

The Jacobi Symbol.

Euler Pseudoprimes.

Zero-Knowledge Proofs.

12. Decimal Fractions and Continued.

Decimal Fractions.

Finite Continued Fractions.

Infinite Continued Fractions.

Periodic Continued Fractions.

Factoring Using Continued Fractions.

13. Some Nonlinear Diophantine Equations.

Pythagorean Triples.

Fermat's Last Theorem.

Sums of Squares.

Pell's Equation.

14. The Gaussian Integers.

Gaussian Primes.

Unique Factorization of Gaussian Integers.

Gaussian Integers and Sums of Squares.