Bibliographic record and links to related information available from the Library of Congress catalog.
Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.
Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii A Word to the Student . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix 1 Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Fundamental Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 The Summation and Product Notations . . . . . . . . . . . . . . . . . . . . . 9 1.3 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.6 Polygonal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.7 Pyramidal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1.8 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.1 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.2 Base-b Representations (optional) . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.3 Operations in Nondecimal Bases (optional) . . . . . . . . . . . . . . . . . . . 91 2.4 Number Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 2.5 Prime and Composite Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2.6 Fibonacci and Lucas Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 2.7 Fermat Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 vii viii Contents Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 3.1 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.3 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . . . . . 175 3.4 Least Common Multiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 3.5 Linear Diophantine Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 4 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 4.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 4.2 Linear Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 4.3 The Pollard Rho Factoring Method . . . . . . . . . . . . . . . . . . . . . . . . . 240 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 5 Congruence Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.1 Divisibility Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.2 Modular Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 5.3 Check Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 5.4 The p-Queens Puzzle (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . 276 5.5 Round-Robin Tournaments (optional) . . . . . . . . . . . . . . . . . . . . . . . 279 5.6 The Perpetual Calendar (optional) . . . . . . . . . . . . . . . . . . . . . . . . . 284 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Contents ix 6 Systems of Linear Congruences . . . . . . . . . . . . . . . . . . . . . . . . 297 6.1 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 297 6.2 General Linear Systems (optional) . . . . . . . . . . . . . . . . . . . . . . . . . 305 6.3 2×2 Linear Systems (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . 309 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 7 Three Classical Milestones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 7.1 Wilson¿s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 7.2 Fermat¿s Little Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 7.3 Pseudoprimes (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 7.4 Euler¿s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 8 Multiplicative Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 8.1 Euler¿s Phi Function Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 8.2 The Tau and Sigma Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 8.3 Perfect Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 8.4 Mersenne Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 8.5 The Möbius Function (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . 400 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 9 Cryptology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 9.1 Affine Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 9.2 Hill Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 9.3 Exponentiation Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 9.4 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 x Contents 9.5 Knapsack Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 10 Primitive Roots and Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 10.1 The Order of a Positive Integer . . . . . . . . . . . . . . . . . . . . . . . . . . 459 10.2 Primality Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 10.3 Primitive Roots for Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 10.4 Composites with Primitive Roots (optional) . . . . . . . . . . . . . . . . . . 478 10.5 The Algebra of Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 11 Quadratic Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 11.1 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 11.2 The Legendre Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 11.3 Quadratic Reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 11.4 The Jacobi Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 11.5 Quadratic Congruences with Composite Moduli (optional) . . . . . . . . 541 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 12 Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 12.1 Finite Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558 12.2 Infinite Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585 Contents xi 13 Miscellaneous Nonlinear Diophantine Equations . . . . . . . . . . 587 13.1 Pythagorean Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 13.2 Fermat¿s Last Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598 13.3 Sums of Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611 13.4 Pell¿s Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636 Computer Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638 Enrichment Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639 A Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 A.1 Proof Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 A.2 Web Sites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 T Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651 T.1 Factor Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 T.2 Values of Some Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . 659 T.3 Least Primitive Roots r Modulo Primes p . . . . . . . . . . . . . . . . . . . . . 662 T.4 Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667 Solutions to Odd-Numbered Exercises . . . . . . . . . . . . . . . . . . . . . . . . 675 Credits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
Library of Congress Subject Headings for this publication:
Number theory.