Elementary Number Theory with Applications (eBook)

Front cover 1
Elementary Number Theory with Applications 6
Copyright page 7
Contents 10
Preface 16
A Word to the Student 24
Chapter 1. Fundamentals 28
1.1 Fundamental Properties 30
1.2 The Summation and Product Notations 36
1.3 Mathematical Induction 42
1.4 Recursion 53
1.5 The Binomial Theorem 59
1.6 Polygonal Numbers 66
1.7 Pyramidal Numbers 76
1.8 Catalan Numbers 79
Chapter Summary 84
Review Exercises 87
Supplementary Exercises 89
Computer Exercises 92
Enrichment Readings 93
Chapter 2. Divisibility 96
2.1 The Division Algorithm 96
*2.2 Base-b Representations (optional) 107
*2.3 Operations in Nondecimal Bases (optional) 116
2.4 Number Patterns 125
2.5 Prime and Composite Numbers 130
2.6 Fibonacci and Lucas Numbers 155
2.7 Fermat Numbers 166
Chapter Summary 170
Review Exercises 173
Supplementary Exercises 175
Computer Exercises 178
Enrichment Readings 180
Chapter 3. Greatest Common Divisors 182
3.1 Greatest Common Divisor 182
3.2 The Euclidean Algorithm 193
3.3 The Fundamental Theorem of Arithmetic 200
3.4 Least Common Multiple 211
3.5 Linear Diophantine Equations 215
Chapter Summary 232
Review Exercises 234
Supplementary Exercises 236
Computer Exercises 237
Enrichment Readings 237
Chapter 4. Congruences 238
4.1 Congruences 238
4.2 Linear Congruences 257
4.3 The Pollard Rho Factoring Method 265
Chapter Summary 267
Review Exercises 268
Supplementary Exercises 270
Computer Exercises 271
Enrichment Readings 272
Chapter 5. Congruence Applications 274
5.1 Divisibility Tests 274
5.2 Modular Designs 280
5.3 Check Digits 286
*5.4 The p-Queens Puzzle (optional) 300
*5.5 Round-Robin Tournaments (optional) 304
*5.6 The Perpetual Calendar (optional) 309
Chapter Summary 315
Review Exercises 316
Supplementary Exercises 318
Computer Exercises 318
Enrichment Readings 319
Chapter 6. Systems of Linear Congruences 322
6.1 The Chinese Remainder Theorem 322
*6.2 General Linear Systems (optional) 330
*6.3 2x2 Linear Systems (optional) 334
Chapter Summary 340
Review Exercises 341
Supplementary Exercises 343
Computer Exercises 345
Enrichment Readings 345
Chapter 7. Three Classical Milestones 348
7.1 Wilson's Theorem 348
7.2 Fermat's Little Theorem 353
*7.3 Pseudoprimes (optional) 364
7.4 Euler's Theorem 368
Chapter Summary 375
Review Exercises 377
Supplementary Exercises 378
Computer Exercises 379
Enrichment Readings 380
Chapter 8. Multiplicative Functions 382
8.1 Euler's Phi Function Revisited 382
8.2 The Tau and Sigma Functions 392
8.3 Perfect Numbers 400
8.4 Mersenne Primes 408
*8.5 The Möbius Function (optional) 425
Chapter Summary 433
Review Exercises 435
Supplementary Exercises 436
Computer Exercises 438
Enrichment Readings 439
Chapter 9. Cryptology 440
9.1 Affine Ciphers 443
9.2 Hill Ciphers 452
9.3 Exponentiation Ciphers 457
9.4 The RSA Cryptosystem 461
9.5 Knapsack Ciphers 470
Chapter Summary 475
Review Exercises 477
Supplementary Exercises 478
Computer Exercises 479
Enrichment Readings 480
Chapter 10. Primitive Roots and Indices 482
10.1 The Order of a Positive Integer 482
10.2 Primality Tests 491
10.3 Primitive Roots for Primes 494
*10.4 Composites with Primitive Roots (optional) 501
10.5 The Algebra of Indices 509
Chapter Summary 516
Review Exercises 518
Supplementary Exercises 519
Computer Exercises 520
Enrichment Readings 520
Chapter 11. Quadratic Congruences 522
11.1 Quadratic Residues 522
11.2 The Legendre Symbol 528
11.3 Quadratic Reciprocity 542
11.4 The Jacobi Symbol 554
*11.5 Quadratic Congruences with Composite Moduli (optional) 562
Chapter Summary 570
Review Exercises 573
Supplementary Exercises 575
Computer Exercises 576
Enrichment Readings 577
Chapter 12. Continued Fractions 578
12.1 Finite Continued Fractions 579
12.2 Infinite Continued Fractions 592
Chapter Summary 602
Review Exercises 603
Supplementary Exercises 605
Computer Exercises 605
Enrichment Readings 605
Chapter 13. Miscellaneous Nonlinear Diophantine Equations 606
13.1 Pythagorean Triangles 606
13.2 Fermat's Last Theorem 617
13.3 Sums of Squares 629
13.4 Pell's Equation 640
Chapter Summary 648
Review Exercises 650
Supplementary Exercises 653
Computer Exercises 655
Enrichment Readings 655
Appendix 658
A.1 Proof Methods 658
A.2 Web Sites 665
Tables 668
T.1 Factor Table 669
T.2 Values of Some Arithmetic Functions 676
T.3 Least Primitive Roots r Modulo Primes p 679
T.4 Indices 680
References 684
Solutions to Odd-Numbered Exercises 692
Chapter 1 Fundamentals 692
Chapter 2 Divisibility 704
Chapter 3 Greatest Common Divisors 715
Chapter 4 Congruences 723
Chapter 5 Congruence Applications 729
Chapter 6 Systems of Linear Congruences 734
Chapter 7 Three Classical Milestones 738
Chapter 8 Multiplicative Functions 745
Chapter 9 Cryptology 755
Chapter 10 Primitive Roots and Indices 758
Chapter 11 Quadratic Congruences 764
Chapter 12 Continued Fractions 773
Chapter 13 Miscellaneous Nonlinear Diophantine Equations 775
Credits 784
Index 788