Contents

1

2

3

4

5

6

7

8

9

10

11

	Notation	xi
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
Quadratic Reciprocity and Quadratic Forms	131
	3.1     Quadratic Residues           131
	3.2     Quadratic Reciprocity           137
	3.3     The Jacobi Symbol           142
	3.4     Binary Quadratic Forms           150
	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.5     Ternary Quadratic Forms            240
	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.5     Quadratic Fields            425
	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
General References	500
Hints	503
Answers	512
Index	522