Contents

1

2

3

4

5

6

7

8

9

10

11

Divisibility

1

1.1     Introduction           1
1.2     Divisibility           4
1.3     Primes           20
1.4     The Binomial Theorem           35
Notes on Chapter 1            44

Congruences

47

2.1     Congruences           47
2.2     Solutions of Congruences           60
2.3     The Chinese Remainder Theorem           64
2.4     Techniques of Numerical Calculation            74
2.5     Public-Key Cryptography           84
2.6     Prime Power Moduli           86
2.7     Prime Modulus           91
2.8     Primitive Roots and Power Residues           97
2.9     Congruences of Degree Two, Prime Modulus           110
2.10   Number Theory from an Algebraic Viewpoint           115
2.11   Groups, Rings, and Fields           121
Notes on Chapter 2           128

131

3.3     The Jacobi Symbol           142
3.5     Equivalence and Reduction of Binary Quadratic Forms           155
3.6     Sums of Two Squares           163
3.7     Positive Definite Binary Quadratic Forms           170
Notes on Chapter 3           176

Some Functions of Number Theory

180

4.1    Greatest Integer Function            180
4.2    Arithmetic Functions            188
4.3     The Möbius Inversion Formula            193
4.4     Recurrence Functions            197
4.5     Combinatorial Number Theory            206
Notes on Chapter 4           211

Some Diophantine Equations

212

5.1     The Equation ax + by  =  c            212
5.2     Simultaneous Linear Equations            219
5.3     Pythagorean Triangles            231
5.4     Assorted Examples            234
5.6     Rational Points on Curves            249
5.7     Elliptic Curves            261
5.8     Factorization Using Elliptic Curves            281
5.9     Curves of Genus Greater Than 1            288
Notes on Chapter 5           289

Farey Fractions and Irrational Numbers

297

6.1     Farey Sequences            297
6.2     Rational Approximation            301
6.3     Irrational Numbers            307
6.4     The Geometry of Numbers            312
Notes on Chapter 6           322

Simple Continued Fractions

325

7.1     The Euclidean Algorithm           325
7.2     Uniqueness           327
7.3     Infinite Continued Fractions           329
7.4     Irrational Numbers           334
7.5     Approximation to Irrational Numbers           336
7.6     Best Possible Approximations           341
7.7     Periodic Continued Fractions           344
7.8     Pell's Equation           351
7.9     Numerical Computation           358
Notes on Chapter 7           359

Primes and Multiplicative Number Theory

360

8.1     Elementary Prime Number Estimates            360
8.2     Dirichlet Series            374
8.3     Estimates of Arithmetic Functions            389
8.4     Primes in Arithmetic Progressions            401
Notes on Chapter 8           406

Algebraic Numbers

409

9.1     Polynomials            410
9.2     Algebraic Numbers            414
9.3     Algebraic Number Fields            419
9.4     Algebraic Integers            424
9.6     Units in Quadratic Fields            428
9.7     Primes in Quadratic Fields            429
9.8     Unique Factorization            431
9.9     Primes in Quadratic Fields Having the Unique Factoriation Property            433
9.10   The Equation x3 + y3  =  z3            441
Notes on Chapter 9           445

The Partition Function

446

10.1     Partitions            446
10.2     Ferrers Graphs            448
10.3     Formal Power Series, Generating Functions, and Euler's Identity            452
10.4     Euler's Formula; Bounds on p(n)            497
10.5     Jacobi's Formula            463
10.6     A Divisibility Property            467
Notes on Chapter 10           471

The Density of Sequences of Integers

472

11.1     Asymptotic Density           473
11.2     Schnirelmann Denstiy and the alpha-beta Theorem           476
Notes on Chapter 11           481

Appendices

482

A.1     The Fundamental Theorem of Algebra           482
A.2     Symmetric Functions           484
A.3     ASpecial Value of the Riemann Zeta Function           490
A.4     Linear Recurrences           493