FUNDAMENTAL NUMBER THEORY WITH APPLICATIONS

Richard A. Mollin

ISBN#: 0-8493-3987-1

Order el ectronically:

TABLE OF CONTENTS:

Review:

A textbook for an undergraduate c ourse at lower-level without and at upper-level with optional sections on applications. Assumes no background in computer science and no mathematics past solid high- school level. Combines elementary number theory with algebraic number theory and applications such as those in cryptology. Begins with the arithmetic of the rational integers and proceeds through quadratic orders to an introduction of algebraic number theory. Also briefly traces the history of number theory from the earliest inscriptions.

Book News, Inc.B., Portland, OR

BRIEF OVERVIEW:

If you want to give an introductory number theory course at any level, then this text is for you. The applications to computer science, especially cryptography, are rich and extensive, ranging from computer arithmetic to an elementary presentation of the elliptic curve factoring method. There are also optional applications to algebraic number theory. A human touch is given by the more than 70 biographies of mathematicians, which are woven through the text as footnotes.

The text is exercise-rich, with over 740 problems, ranging from the routine to the more difficult star problems, and all odd numbered exercises are solved in detail at the end of the text. To aid the instructor who adopts the text for a course, a solutions manual for the even numbered exercises is available free of charge.

There are over 270 examples illustrating and motivating all topics covered, as well as 9 appendices chock-full of information ranging from set theory to Cunningham factorizations, and new records. The index has over one thousand entries to ensure maximum ease in extracting information.

Ron Evans, who is using the text in a course at UCSD, has commented: "Both the student and the instructor alike will be impressed with the quality, variety and number of stimulating exercises.

Steve Galovich says of the text: "The book is engaging, and I am sure that students will learn a great deal from it."

Andrew Granville says: "I like the chatty style and the human touch that are evident throughout the text. I especially enjoyed reading the frequent historical notes, bringing back to life many of the great mathematicians by amusing and pertinent anecdotes. "

Irving Kaplansky has written to this author indicating that he was motivated to do new research on continued fractions and Diophantine equations by the "pretty theorem" given on page 348. He found the book both "stimulating and informative".

Nikos Tzanakis says: "This is a new book written by an active number-theorist, who has very refreshing views about how basic number theory should be presented to beginners and advanced students. Actually, it is so rich that the instructor can find many interesting paths through its pages in order to teach not only the basic theory, but also more advanced topics and applications. The author dares to include topics, which are rarely found in "elementary" books, and he does this successfully. I wouldn't hesitate to say that it may be a breakthrough for "elementary" number theory books, starting with the title, which is very well chosen."

Detailed Description from the PREFACE:

This text is structured for an undergraduate course in number theory at any level. The last two sections of each chapter are marked by the pointing hand symbol to denote that they are the optional sections on applications. The penultimate section of each chapter is devoted to applications in computer science, especially to cryptography. The last section of each chapter develops applications to algebraic number theory via quadratics, meaning applications to quadratic fields and quadratic orders in general. The student who works through these last interconnected sections of each chapter will have a solid foundation and introduction to an upper level algebraic number theory course. The remaining sections of each chapter constitute the core material (plus some added gems, and more challenging material marked by the pencil symbol to distinguish them from the essential core material), for what is usually termed a course in Elementary Number Theory. The interrelated penultimate sections of each chapter provide a mini-course in aspects of computer science related to cryptography, factoring, primality testing, complexity analysis, computer arithmetic, and computational number theory in general. No background in computer science is assumed, so the elementary approach will appeal to anyone, however uninitiated, who is interested in learning about these areas. Computer scientists, engineers, mathematicians, and students in science will also find that these sections provide a quick introduction to these applications of number theory.

The instructor may gear the text for an upper-division course in number theory by covering the fundamentals plus any choice of the applications in the last two sections of each chapter. On the other hand, the text is also intended for a lower-division introductory number theory course. In this case, the instructor may cover only the core material with perhaps an application or two for extra interest from the sections marked by the pointing hand, or some of the more challenging non-core material markedby the pencil symbol.

For the beginner, which may include enlightened high school students, we have made no assumptions as to the background of the reader starting in the Introduction in Section One of Chapter One. We begin there with a history of number theory going back to the ancient Sumerians in the fourth millennium B.C. We continue this historical thread throughout the text. We explore, for example, the very notions of number and addition, among other primitive notions in this introduction to set the stage for the fundamental laws of arithmetic that follow in the subsequent section, and we build from there. Hence, the complete novice can use the text as a self-contained entity. The text is flexible enough to satisfy disparate needs in the presentation of number theory at any level.

Features of This Text

The book is exercise-rich with over 740 problems. The more challenging exercises are marked with the star symbol. Also, complete and detailed solutions to all of the odd-numbered exercises are given in the back of the text. Numerous topics not covered in the main text are introduced via the exercises. For example, we introduce Carmichael numbers, Dirichlet products, Jacobsthal sums, Mersenne primes, perfect numbers, powerful numbers, and self-contained numbers, to mention only a few. Also, the exercises introduce some entertaining games not covered in the main text, such as the coconut problem, the ancient Chinese game of Nim, the tower of Hanoi problem, the egg-basket problem, as well as many others. Finally, there are deeper concepts introduced in the exercises of the optional sections, such as groups, rings, modules and fields at the end of Chapter One. In this way, the reader with little background in abstract algebra may work through these exercises and achieve a grounding necessary to understand some of the topics in the optional last sections of later chapters. Hence, the exercises serve the triple purpose of testing knowledge of concepts covered in the text, introducing interesting new topics, and providing a venue for the uninitiated to learn some background material in order to proceed to study some of the optional sections, if so desired.

There are over two hundred and seventy examples in the text. Examples are essential for clarification, and illustration of theoretical concepts, and no effort has been spared in placing them in appropriate places for maximum benefit.

The text is accessible to anyone from the novice to the research scientist. The novice is led through the basics starting in Chapter One, by introducing fundamentals as they are needed and moving layer by layer to the more involved concepts. In this way, mathematical maturity is gradually achieved as we proceed deeper into the text. The more experienced reader is reminded of the salient features of the fundamentals, and led to deeper concepts via the more challenging exercises and other material in the optional applications in the last two sections of each chapter.

An introduction to logic and methods of proof begins in Section Two of Chapter One. Rather than having an appendix with discussion of logical principles, we develop them as we need them and discuss them as they arise. For instance, proof by contradiction is introduced just before it is used to prove Dirichlet's Box Principle. Before that, the first formal proof in the text is given for the Theorem on properties of the summation notation. Then in a Remark, we discuss what constitutes a proof, what should be observed in the construction of a proof, and discuss implications, equivalent statements, and contrapositives, among others. Rules and stylistic concerns are also addressed. In this fashion, we build the necessary tools as they are needed.

Non-standard methods of proof for fundamental results are presented whenever possible. For instance, Thue's Theorem is used to give a short proof of Lagrange's Four Square Theorem. The development of Thue's Theorem is not normally considered part of a course in introductory number theory, but we have presented a short proof of it, and are able to use it effectively throughout.

Motivation is critical, and all proofs are motivated by one of the more than one thousand exercises and examples, as discussed above.

Induction is treated at great length in Chapter One. This has always been a sore point for the beginning student, so we discuss "what induction really means". Later, we develop several more illustrative proofs using induction, and have dozens of exercises throughout to test understanding of the concept.

There are more than seventy biographies of the mathematicians who helped shape the structure of number theory throughout the ages. These are given primarily, but not exclusively, in the footnotes woven throughout the text, to give human depth to the mathematics being presented. Our understanding of number theory should be coupled with an understanding of the figures who helped us achieve this magnificent edifice of human thought. The footnote presentation of them allows the reader to treat them as digressions, and access them at will without significantly interfering with the main mathematical text.

The applications to computer science via cryptography, primality testing, factoring methods, complexity analysis, computer arithmetic, and computational number theory in general is wide ranging. For instance, we cover the following primality tests in detail: the elliptic curve test, the Lucas test, the Miller-Selfridge-Rabin test, Pepin's test, Rabin's probabilistic test, and the Solovay-Strassen test, coupled with the random number generators: linear congruential generator, and pseudo-random RSA number generator.

We also cover in detail the following factoring methods: the continued fraction method, the elliptic curve method, Pollard's p-1 method, Pollard's rho method, and the quadratic sieve method.

For the reader who is not well-versed in computer arithmetic, Section Five of Chapter One provides a self-contained means of learning the basics. Furthermore, complexity analysis is developed from the basics therein, so that even the novice reader may follow developments in later chapters by working through the relevant details in that section.

A sampling of what we cover in terms of cryptography is given by: affine cryptosystems, exponentiation ciphers, public key cryptosystems, including the RSA cipher, and more.

Numerous new records, open problems, and solutions of outstanding problems are cited throughout the text. For instance, the proof of the infinitude of Carmichael numbers is discussed, along with some open related problems. Also, the solution of Fermat's Last Theorem is discussed in relation to the open ABC Conjecture. The newly discovered Mersenne prime with almost 421,000 digits is discussed in Appendix C, as well as in the exercises.

Complete solutions of Diophantine equation x^2-Dy^2=n for D>0 are given in via a non-standard approach using what we call semi-simple continued fractions. The classical approach via reduction to the case where the disciminant is less than the square root of n is also featured.

The appendices are chock-full of information not normally found in an introductory number theory text. In this age of symbolic-algebraic-manipulation software packages, such as Maple, available to students and scientists alike, there is little need for large factor tables or their kin. Instead, we have opted for an approach of novelty and information gathering in number theory that this author has wanted to see in one place for some time. We have Set Theory in Appendix A for those readers unfamiliar with the basics, or wanting a refresher. Nevertheless, even for the well-versed, we go a distance further by discussing the Axiom of choice, and Zorn's Lemma. In Appendix B, we have all primes and their primitive roots to almost ten thousand. Despite the above caveat about large tables of values, this author has found that having a table of primes, together with their primitive roots at a glance to be a valuable, convenient tool. In Appendix C, we have tables of Fermat primes, Mersenne primes, repunit primes, and Wieferich primes, as well as a brief discussion of Bertrand's postulate. In Appendix D, we have examples of Cunningham factorizations. Appendix E presents tables of pseudoprimes and Carmichael numbers, while Appendix F displays some examples of indices of integers to prime modulii. Appendix G contains some tabulated values of Euler's totient function, the number of divisors function, the sum of divisors function, and the Mobius function. Appendix H features a brief discussion of the power of the ABC Conjecture, and Appendix I closes the text with a discussion of a centerpiece of number theory, the Prime Number Theorem.

The list of symbols is exactly one page, of the most important and frequently used symbols. Thus, the reader may determine, at a glance, on which page the first defining occurrence of a desired notation exists. Every effort has been made to reduce the excessive use of notation. Hence, we have only one page of the most essential symbols used throughout the text.

The index has over one thousand entries, and has been devised in such a way to ensure that there is maximum ease in getting information from the text. For instance, the reader will never look up an entry x and see the phrase x: see entry y. There is maximum cross-referencing to ensure that the reader will not be burdened. An end goal is a self-contained text that is easy to use by anyone from the novice to the research scientist.

Given over 320 unworked even numbered exercises, the Solutions Manual for Even Numbered Exercises will be found to be indispensible. It is available without charge, from the publisher, to adopters of this text.

Online updates page for typos, comments, etc.

Return to R.A.Mollin's homepage

Last modified: January 21, 2005.