An introduction to the theory of numbers

Title ......Page 1
Copyright ......Page 2
Preface ......Page 3
Contents ......Page 5
Notation ......Page 9
1.1 INTRODUCTION ......Page 13
1.2 DIVISIBILITY ......Page 16
PROBLEMS ......Page 29
1.3 PRIMES ......Page 32
PROBLEMS ......Page 40
1.4 THE BINOMIAL THEOREM ......Page 47
PROBLEMS ......Page 52
NOTES ON CHAPTER 1 ......Page 56
2.1 CONGRUENCES ......Page 59
PROBLEMS ......Page 68
2.2 SOLUTIONS OF CONGRUENCES ......Page 72
PROBLEMS ......Page 74
2.3 THE CHINESE REMAINDER THEOREM ......Page 76
PROBLEMS ......Page 83
2.4 TECHNIQUES OF NUMERICAL CALCULATION ......Page 86
PROBLEMS ......Page 94
2.5 PUBLIC-KEY CRYPTOGRAPHY ......Page 96
2.6 PRIME POWER MODULI ......Page 98
2.7 PRIME MODULUS ......Page 103
PROBLEMS ......Page 108
2.8 PRIMITIVE ROOTS AND POWER RESIDUES ......Page 109
PROBLEMS ......Page 118
2.9 CONGRUENCES OF DEGREE TWO, PRIME MODULUS ......Page 122
PROBLEMS ......Page 126
2.10 NUMBER THEORY FROM AN ALGEBRAIC VIEWPOINT ......Page 127
PROBLEMS ......Page 131
2.11 GROUPS, RINGS, AND FIELDS ......Page 133
PROBLEMS ......Page 138
NOTES ON CHAPTER 2 ......Page 140
3.1 QUADRATIC RESIDUES ......Page 143
PROBLEMS ......Page 147
3.2 QUADRATIC RECIPROCITY ......Page 149
PROBLEMS ......Page 152
3.3 THE JACOBI SYMBOL ......Page 154
PROBLEMS ......Page 159
3.4 BINARY QUADRATIC FORMS ......Page 162
PROBLEMS ......Page 166
3.5 EQUIVALENCE AND REDUCTION OF BINARY QUADRATIC FORMS ......Page 167
PROBLEMS ......Page 174
3.6 SUMS OF TWO SQUARES ......Page 175
PROBLEMS ......Page 181
3.7 POSITIVE DEFINITE BINARY QUADRATIC FORMS ......Page 182
NOTES ON CHAPTER 3 ......Page 188
4.1 GREATEST INTEGER FUNCTION ......Page 192
PROBLEMS ......Page 196
4.2 ARITHMETIC FUNCTIONS ......Page 200
PROBLEMS ......Page 203
4.3 THE MOBIUS INVERSION FORMULA ......Page 205
PROBLEMS ......Page 207
4.4 RECURRENCE FUNCTIONS ......Page 209
PROBLEMS ......Page 216
4.5 COMBINATORIAL NUMBER THEORY ......Page 218
PROBLEMS ......Page 222
NOTES ON CHAPTER 4 ......Page 223
5.1 THE EQUATION ax + by = c ......Page 224
PROBLEMS ......Page 230
5.2 SIMULTANEOUS LINEAR EQUATIONS ......Page 231
PROBLEMS ......Page 241
5.3 PYTHAGOREAN TRIANGLES ......Page 243
PROBLEMS ......Page 245
5.4 ASSORTED EXAMPLES ......Page 246
PROBLEMS ......Page 251
5.5 TERNARY QUADRATIC FORMS ......Page 252
PROBLEMS ......Page 260
5.6 RATIONAL POINTS ON CURVES ......Page 261
PROBLEMS ......Page 272
5.7 ELLIPTIC CURVES ......Page 273
PROBLEMS ......Page 290
5.8 FACTORIZATION USING ELLIPTIC CURVES ......Page 293
PROBLEMS ......Page 299
5.9 CURVES OF GENUS GREATER THAN 1 ......Page 300
NOTES ON CHAPTER 5 ......Page 301
6.1 FAREY SEQUENCES ......Page 309
PROBLEMS ......Page 312
6.2 RATIONAL APPROXIMATIONS ......Page 313
6.3 IRRATIONAL NUMBERS ......Page 319
PROBLEMS ......Page 323
6.4 THE GEOMETRY OF NUMBERS ......Page 324
PROBLEMS ......Page 331
NOTES ON CHAPTER 6 ......Page 334
7.1 THE EUCLIDEAN ALGORITHM ......Page 337
7.2 UNIQUENESS ......Page 339
7.3 INFINITE CONTINUED FRACTIONS ......Page 341
PROBLEMS ......Page 345
7.4 IRRATIONAL NUMBERS ......Page 346
7.5 APPROXIMATIONS TO IRRATIONAL NUMBERS ......Page 348
PROBLEMS ......Page 352
7.6 BEST POSSIBLE APPROXIMATIONS ......Page 353
7.7 PERIODIC CONTINUED FRACTIONS ......Page 356
7.8 PELL'S EQUATION ......Page 363
PROBLEMS ......Page 368
7.9 NUMERICAL COMPUTATION ......Page 370
NOTES ON CHAPTER 7 ......Page 371
8.1 ELEMENTARY PRIME NUMBER ESTIMATES ......Page 372
PROBLEMS ......Page 385
8.2 DIRICHLET SERIES ......Page 386
PROBLEMS ......Page 399
8.3 ESTIMATES OF ARITHMETIC FUNCTIONS ......Page 401
PROBLEMS ......Page 410
8.4 PRIMES IN ARITHMETIC PROGRESSIONS ......Page 413
PROBLEMS ......Page 417
NOTES ON CHAPTER 8 ......Page 418
CHAPTER 9: Algebraic Numbers ......Page 421
9.1 POLYNOMIALS ......Page 422
9.2 ALGEBRAIC NUMBERS ......Page 426
9.3 ALGEBRAIC NUMBER FI ......Page 431
PROBLEMS ......Page 435
9.4 ALGEBRAIC INTEGERS ......Page 436
9.5 QUADRATIC FIELDS ......Page 437
PROBLEMS ......Page 439
9.6 UNITS IN QUADRATIC FIELDS ......Page 440
9.7 PRIMES IN QUADRATIC FIELDS ......Page 441
9.8 UNIQUE FACTORIZATION ......Page 443
PROBLEMS ......Page 444
9.9 PRIMES IN QUADRATIC FIELDS HAVING THE UNIQUE FACTORIZATION PROPERTY ......Page 445
PROBLEMS ......Page 452
9.10 THE EQUATION x 3 + y3 = Z3 ......Page 453
NOTES ON CHAPTER 9 ......Page 457
10.1 PARTITIONS ......Page 458
PROBLEMS ......Page 459
10.2 FERRERS GRAPHS ......Page 460
PROBLEMS ......Page 462
10.3 FORMAL POWER SERIES, GENERATING FUNCTIONS, AND EULER'S IDENTITY ......Page 464
10.4 EULER'S FORMULA; BOUNDS ON p(n) ......Page 469
10.5 JACOBI'S FORMULA ......Page 475
NOTES ON CHAPTER 10 ......Page 483
CHAPTER 11: The Density of Sequences of Integers ......Page 484
11.1 ASYMPTOTIC DENSITY ......Page 485
PROBLEMS ......Page 487
11.2 SCHNIRELMANN DENSITY AND THE aß THEOREM ......Page 488
NOTES ON CHAPTER 11 ......Page 493
A.I THE FUNDAMENTAL THEOREM OF ALGEBRA ......Page 494
PROBLEMS ......Page 501
A.3 A SPECIAL VALUE OF THE RIEMANN ZETA FUNCTION ......Page 502
PROBLEMS ......Page 503
A.4 LINEAR RECURRENCES ......Page 505
PROBLEMS ......Page 510
General References ......Page 512
Hints ......Page 515
Answers ......Page 524
Index ......Page 534