Preface page ix

1 The intriguing natural numbers

1.1 Polygonal numbers 1

1.2 Sequences of natural numbers 23

1.3 The principle of mathematical induction 40

1.4 Miscellaneous exercises 43

1.5 Supplementary exercises 50

2 Divisibility

2.1 The division algorithm 55

2.2 The greatest common divisor 64

2.3 The Euclidean algorithm 70

2.4 Pythagorean triples 76

2.5 Miscellaneous exercises 81

2.6 Supplementary exercises 84

3 Prime numbers

3.1 Euclid on primes 87

3.2 Number theoretic functions 94

3.3 Multiplicative functions 103

3.4 Factoring 108

3.5 The greatest integer function 112

3.6 Primes revisited 115

3.7 Miscellaneous exercises 129

3.8 Supplementary exercises 133

4 Perfect and amicable numbers

4.1 Perfect numbers 136

4.2 Fermat numbers 145

4.3 Amicable numbers 147

4.4 Perfect-type numbers 150

4.5 Supplementary exercises 159

5 Modular arithmetic

5.1 Congruence 161

5.2 Divisibility criteria 169

5.3 Euler’s phi-function 173

5.4 Conditional linear congruences 181

5.5 Miscellaneous exercises 190

5.6 Supplementary exercises 193

6 Congruences of higher degree

6.1 Polynomial congruences 196

6.2 Quadratic congruences 200

6.3 Primitive roots 212

6.4 Miscellaneous exercises 222

6.5 Supplementary exercises 223

7 Cryptology

7.1 Monoalphabetic ciphers 226

7.2 Polyalphabetic ciphers 235

7.3 Knapsack and block ciphers 245

7.4 Exponential ciphers 250

7.5 Supplementary exercises 255

8 Representations

8.1 Sums of squares 258

8.2 Pell’s equation 274

8.3 Binary quadratic forms 280

8.4 Finite continued fractions 283

8.5 Infinite continued fractions 291

8.6 p-Adic analysis 298

8.7 Supplementary exercises 302

9 Partitions

9.1 Generating functions 304

9.2 Partitions 306

9.3 Pentagonal Number Theorem 311

9.4 Supplementary exercises 324

Tables

T.1 List of symbols used 326

T.2 Primes less than 10 000 329

T.3 The values of τ(n), σ(n), φ(n), μ(n), ω(n), and Ω(n) for natural numbers less than or equal to 100 333

Answers to selected exercises 336

Bibliography

Mathematics (general) 411

History (general) 412

Chapter references 413

Index