You are here

Topics in the Theory of Numbers

Paul Erdös and János Surányi
Publication Date: 
Number of Pages: 
Undergraduate Texts in Mathematics
[Reviewed by
Donald L. Vestal
, on

This Springer publication is the English translation of the second edition of Erdös and Surányi’s 1959 book. The second edition came out in 1995, with some new chapters and updated results. This translation, done by Barry Guikuli, with some assistance by Romy Varga, was completed in 2000, four years after the death of Paul Erdös. If you don’t know who Erdös is, check out The Man Who Loved Only Numbers or My Brain in Open. (And if you are a mathematician who doesn’t know who Paul Erdös is..., well, shame on you!)

As the (less-than-descriptive) title suggests, this book deals with number theory, or more specifically, several subareas of number theory, which I detail below. The purpose of the book is to present some of the relatively recent results in these different areas, and to highlight some of the results of Erdös. However, even though some fairly advanced results are presented, the authors don’t take much for granted: each topic is built, for the most part, from basic principles. The reader is then taken on a whirlwind tour of the advanced results.

The first section in the book is a brief statement of ten facts that are used in this book, without proof. The facts are standard results from combinatorics and analysis, things like the binomial theorem, or the fact that log x grows slower than any positive power of x. (Actually, I wish more texts did this.)

Chapter 1 covers "Divisibility, the Fundamental Theorem of Number Theory." As the title suggests, we’re starting from first principles. The authors give the Remainder Theorem (aka the Division Algorithm) followed by a set of problems. Many of the usual basic properties of divisibility are proven, although not always in the standard way. The authors make use of the Four Number Theorem:

If a and b are positive numbers and c and d are positive integers such that ab = cd, then there exists a positive number r and positive integers s, t, and u such that the following equalities hold: a = rs, b = tu, c = rt, d = su. If, in addition, a and c are integers, then r may be taken to be an integer.

The proof presented is a geometric argument. (In fact, the authors use geometry quite a bit in this book.) From this theorem, we get many divisibility results, including prime factorization and the Fundamental Theorem of Arithmetic (which is what it’s called in the text, despite the name of the chapter). We also get results about the least common multiple, prime factorization of factorials, a complete description of Pythagorean triples, sums of two squares, the Euclidean algorithm, and the two-variable linear Diophantine equation. As mentioned before, most of this is standard elementary number theory.

Chapter 2 (which was added to the second edition of the book) deals with "Congruences." Once again, we start from first principles. Some basic properties of congruences are derived, including divisibility rules for 9 and 11, and the notion of residue classes modulo m. The authors then mention the ideas of disjoint and covering systems of congruences. Some examples are given, along with the current state of affairs. For example, we are told that covering systems with smallest modulus 3, 4, 6, 8, 9, and 20 exist, the names of mathematicians who created them, and that

We do not know whether for an arbitrary m0 there exists such a covering system with smallest modulus m0. To date, we do not even know the answer for all m0 less than 20, nor do we know whether there exists a covering system for which every modulus is odd.

In the exercises following this section, the reader is told to prove that for a covering system, the sum of the reciprocals of the moduli is at least one. Keep in mind, this is a mere eight pages after the introduction of the definition of congruence! The authors’ goal seems to be to make a beeline from the basic principles to the current state of affairs. Not a problem if you’re an experienced mathematician, but probably not something you would want to subject an undergraduate to. We are then given results about solutions to linear congruences and the Chinese Remainder Theorem. Then we get a proof about "reclusive primes:"

"For any given number N, there exists a prime number that is at least N greater than the previous prime number and at least N smaller than the following one."

The proof makes clever use of the Chinese Remainder Theorem, and Dirichlet’s theorem on primes in an arithmetic progression (a proof of this is not given, just a reference). There is some discussion of the Euler phi function, including Fermat’s Little Theorem and Euler’s Theorem. The authors use Euler’s Theorem to show how the RSA encryption scheme works (although they do this without even mentioning RSA or the names Rivest, Shamir, and Adleman). The remainder of the chapter involves standard material: residue classes, polynomial congruences, Wilson’s Theorem, the Legendre symbol, and quadratic reciprocity.

Chapter 3, titled "Rational and Irrational Numbers. Approximation of Numbers by Rational Numbers (Diophantine Approximation)," deals with Diophantine Approximation (which would have been a better title). Once again, we start out slow, dealing with the decimal expansion of a real number, and how that expansion might tell us about whether the number is rational or irrational. The irrationality of the square root of m2 + 1 for any integer m is established using a geometric argument. A trigonometric series is used to prove that tan(π/m) is irrational for all integers m larger than 4. And the series for e is used to show that e is irrational. Some results on transcendental numbers are given, and the chapter closes with a summary of some of the work (no proofs included) of Roth, Thue, Siegel, Mahler, Baker, and others.

Chapter 4 deals with "Geometric Methods in Number Theory." The authors discuss lattices and the notion of parallelogram lattices. They give the standard result about what kind of polygons can occur in a parallelogram lattice, as well as some properties of lattices, including Pick’s Theorem and Minkowski’s Theorem. The properties are then used to establish results involving Diophantine Approximation and sums of squares (similar to Burger’s chapters on the Geometry of Numbers in Exploring the Number Jungle). The chapter closes with a study of inhomogeneous lattices and divided cells.

Chapter 5 deals with "Properties of Prime Numbers." The chapter begins with a summary (no proofs) of some results concerning the difference between consecutive primes. The authors give a proof that the sum of the reciprocals of the primes diverges. They also prove Chebyshev’s result for the π(x) function (which counts the number of primes less than or equal to x). They next prove Bertrand’s Conjecture (that there always exists a prime between n and 2n). Some mention is made concerning the history of the Prime Number Theorem. Once again Dirichlet’s theorem on primes in an arithmetic sequence is mentioned, and the authors supply proofs for special cases of Dirichlet’s theorem.

Chapter 6 covers "Sequences of Integers." The authors use the Euclidean algorithm to introduce the Fibonacci sequence. They then discuss the idea of the upper and lower density of a sequence. The remainder of the chapter deals with some of the ideas in additive number theory:

  • How to partition the first N integers into r sets so that no two numbers and their difference occur in the same set;
  • The finite version of Fermat’s Last Theorem;
  • Erdös and Turan’s discovery of the fact that however we chose 2k + 1 distinct positive integers, if we take all pairwise sums, then at least k + 1 primes occur as prime divisors of these numbers (along with some recent variations of this theorem);
  • The notion of M-sequences (sequences in which no member is a multiple of another);
  • The notion of T-sequences (sequences which do not contain arithmetic progressions of length 3);
  • The notion of Sidon sequences (sequences of nonnegative integers with the property that all pairwise sums of elements are distinct).

As before, some fairly advanced results are proven, but all deduced from basic principles.

Chapter 7 delves back into "Diophantine Problems." A general solution is given for the Pythagorean n-tuple problem (x12 + x22 + ... + xn2 = yn) . The standard results concerning sums of squares (when is n a sum of two squares, a sum of three squares, or a sum of four squares) are proven. The authors then turn to higher powers, mentioning Waring’s problem, and the values of g(k) (the smallest number of kth powers needed to represent every positive integer), G(k) (the number of kth powers needed to represent every large enough positive integer and such that there are infinitely many integers which can not be expressed using less than G(k) kth powers), and w(k) (the smallest number of kth powers needed to represent every positive integer by adding and subtracting kth powers). The chapter ends with an exploration on whether binomial coefficients can be perfect powers, with some related results.

Chapter 8 returns to the topic of "Arithmetic Functions." We get a probabilistic argument for the equation of the Euler phi function. This is followed by some results on the sigma function, including the notion of Mersenne primes, and perfect, abundant, and deficient numbers. This includes proofs of Euclid’s classification of the even perfect numbers, and the fact that for any s, there are at most finitely many odd perfect numbers with exactly s distinct prime factors. Many advanced results concerning the arithmetic functions mentioned above are proven, along with the two omega functions (which count the number of distinct primes dividing n, and the sum of the powers of the distinct primes dividing n). The remainder of this chapter gets into some fairly heavy analysis.

Following the last chapter, there is a section with hints to some of the more difficult problems in the exercises. (One note of caution: the hints to problems 31 and 32 of Chapter 8 are labeled as 30 and 31.)

The only negative thing I would say about the book involves the presentation. The sections in each chapter are numbered 1, 2, 3, etc, but the authors don’t start each new section on a new page or even with a title. When section 1 ends, it is immediately followed by either a set of problems or by section 2. The sections aren’t given titles, although in the Table of Contents, a description of each section is given. It might have been beneficial to the reader to place this description at the beginning of the section. (In fact, the layout of each chapter, presented in the Table of Contents, is a better guide than the text itself.) It seems that the authors, however, want the prose to flow from one section to the next, without any interruption (except for the occasional problem set). Another concern is the fact that the problems are numbered the same way (1, 2, 3, etc). Each set of problems is clearly labeled with "Exercises," and each problem is indented, so there is some difference between how the sections and exercises are presented. But it is somewhat subtle. All things considered, these are relatively minor flaws (presumably not the kind of presentation which is to be found in The Book).

This book is part of the Undergraduate Texts in Mathematics series, but that may be stretching the term "undergraduate." If you are interested in any of the topics listed above, you’ll almost certainly enjoy this book. If you’re not a big fan of number theory (assuming such people exist!), then you won’t find much here to enjoy.

Donald L. Vestal is Assistant Professor of Mathematics at Missouri Western State College. His interests include number theory, combinatorics, reading, and listening to the music of Rush. He can be reached at

Preface * Facts Used Without Proof in the Book * Divisibility, the Fundamental Theorem of Number Theory * Congruences * Rational and irrational numbers. Approximation of numbers by rational numbers. (Diophantine approximation.) * Geometric methods in number theory * Properties of prime numbers * Sequences of integers * Diophantine Problems * Arithmetic Functions * Hints to the more difficult exercises * Bibliography * Index