Notation xiii

made a conscious effort to document original sources and thus encourage

conformance to Abel’s advice to “read the masters”.

While the study of elementary methods in number theory is one of the

most accessible branches of mathematics, the lack of suitable textbooks

has been a repellent to potential students. It is hoped that this modest

contribution will help to reverse this injustice.

Paul Pollack

Notation

While most of our notation is standard and should be familiar from an intro-

ductory course in number theory, a few of our conventions deserve explicit

mention: The set N of natural numbers is the set {1, 2, 3, 4,...}. Thus 0 is

not considered a natural number. Also, if n ∈ N, we write “τ(n)” (instead

of “d(n)”) for the number of divisors of n. This is simply to avoid awkward

expressions like “d(d)” for the number of divisors of the natural number d.

Throughout the book, we reserve the letter p for a prime variable.

We remind the reader that “A = O(B)” indicates that |A| ≤ c|B| for

some constant c 0 (called the implied constant); an equivalent notation is

“A B”. The notation “A B” means B A, and we write “A B” if

both A B and A B. If A and B are functions of a single real variable

x, we often speak of an estimate of this kind holding as “x → a” (where a

belongs to the two-point compactification R∪{±∞} of R) to mean that the

estimate is valid on some deleted neighborhood of a. Subscripts on any of

these symbols indicate parameters on which the implied constants (and, if

applicable, the deleted neighborhoods) may depend. The notation “A ∼ B”

means A/B → 1 while “A = o(B)” means A/B → 0; here subscripts indicate

parameters on which the rate of convergence may depend.

If S is a subset of the natural numbers N, the (asymptotic, or natural)

density of S is defined as the limit

lim

x→∞

1

x

#{n ∈ S : n ≤ x},

provided that this limit exists. The lower density and upper density of S

are defined similarly, with lim inf and lim sup replacing lim (respectively).

We say that a statement holds for almost all natural numbers n if it holds

on a subset of N of density 1.

If f and G are defined on a closed interval [a, b] ⊂ R, with f piecewise

continuous there, we define

(0.1)

b

a

f(t) dG(t) := G(b)f(b) − G(a)f(a) −

b

a

f (t)G(t) dt,