You are previewing Elementary Number Theory with Programming.
O'Reilly logo
Elementary Number Theory with Programming

Book Description

A highly successful presentation of the fundamental concepts of number theory and computer programming

Bridging an existing gap between mathematics and programming, Elementary Number Theory with Programming provides a unique introduction to elementary number theory with fundamental coverage of computer programming. Written by highly-qualified experts in the fields of computer science and mathematics, the book features accessible coverage for readers with various levels of experience and explores number theory in the context of programming without relying on advanced prerequisite knowledge and concepts in either area.

Elementary Number Theory with Programming features comprehensive coverage of the methodology and applications of the most well-known theorems, problems, and concepts in number theory. Using standard mathematical applications within the programming field, the book presents modular arithmetic and prime decomposition, which are the basis of the public-private key system of cryptography. In addition, the book includes:

  • Numerous examples, exercises, and research challenges in each chapter to encourage readers to work through the discussed concepts and ideas

  • Select solutions to the chapter exercises in an appendix

  • Plentiful sample computer programs to aid comprehension of the presented material for readers who have either never done any programming or need to improve their existing skill set

  • A related website with links to select exercises

  • An Instructor's Solutions Manual available on a companion website

  • Elementary Number Theory with Programming is a useful textbook for undergraduate and graduate-level students majoring in mathematics or computer science, as well as an excellent supplement for teachers and students who would like to better understand and appreciate number theory and computer programming. The book is also an ideal reference for computer scientists, programmers, and researchers interested in the mathematical applications of programming.

    Table of Contents

    1. COVER
    2. TITLE PAGE
    3. PREFACE
    4. WORDS
    5. NOTATION IN MATHEMATICAL WRITING AND IN PROGRAMMING
    6. 1 SPECIAL NUMBERS: TRIANGULAR, OBLONG, PERFECT, DEFICIENT, AND ABUNDANT
      1. TRIANGULAR NUMBERS
      2. OBLONG NUMBERS AND SQUARES
      3. DEFICIENT, ABUNDANT, AND PERFECT NUMBERS
      4. EXERCISES
    7. 2 FIBONACCI SEQUENCE, PRIMES, AND THE PELL EQUATION
      1. PRIME NUMBERS AND PROOF BY CONTRADICTION
      2. PROOF BY CONSTRUCTION
      3. SUMS OF TWO SQUARES
      4. BUILDING A PROOF ON PRIOR ASSERTIONS
      5. SIGMA NOTATION
      6. SOME SUMS
      7. FINDING ARITHMETIC FUNCTIONS
      8. FIBONACCI NUMBERS
      9. AN INFINITE PRODUCT
      10. THE PELL EQUATION
      11. GOLDBACH’S CONJECTURE
      12. EXERCISES
    8. 3 PASCAL’S TRIANGLE
      1. FACTORIALS
      2. THE COMBINATORIAL NUMBERS <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i> CHOOSE CHOOSE <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">k</i>
      3. PASCAL’S TRIANGLE
      4. BINOMIAL COEFFICIENTS
      5. EXERCISES
    9. 4 DIVISORS AND PRIME DECOMPOSITION
      1. DIVISORS
      2. GREATEST COMMON DIVISOR
      3. DIOPHANTINE EQUATIONS
      4. LEAST COMMON MULTIPLE
      5. PRIME DECOMPOSITION
      6. SEMIPRIME NUMBERS
      7. WHEN IS A NUMBER AN <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">m</i>TH POWER?TH POWER?
      8. TWIN PRIMES
      9. FERMAT PRIMES
      10. ODD PRIMES ARE DIFFERENCES OF SQUARES
      11. WHEN IS <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i> A LINEAR COMBINATION OF A LINEAR COMBINATION OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">a</i> AND AND <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">b</i>??
      12. PRIME DECOMPOSITION OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i>!!
      13. NO NONCONSTANT POLYNOMIAL WITH INTEGER COEFFICIENTS ASSUMES ONLY PRIME VALUES
      14. EXERCISES
    10. 5 MODULAR ARITHMETIC
      1. CONGRUENCE CLASSES MOD <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">k</i>
      2. LAWS OF MODULAR ARITHMETIC
      3. MODULAR EQUATIONS
      4. FERMAT’S LITTLE THEOREM
      5. FERMAT’S LITTLE THEOREM
      6. MULTIPLICATIVE INVERSES
      7. WILSON’S THEOREM
      8. WILSON’S THEOREM
      9. WILSON’S THEOREM (2ND VERSION)
      10. SQUARES AND QUADRATIC RESIDUES
      11. LAGRANGE’S THEOREM
      12. LAGRANGE’S THEOREM
      13. REDUCED PYTHAGOREAN TRIPLES
      14. CHINESE REMAINDER THEOREM
      15. CHINESE REMAINDER THEOREM
      16. EXERCISES
    11. 6 NUMBER THEORETIC FUNCTIONS
      1. THE <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">TAU</i> FUNCTION FUNCTION
      2. THE <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">SIGMA</i> FUNCTION FUNCTION
      3. MULTIPLICATIVE FUNCTIONS
      4. PERFECT NUMBERS REVISITED
      5. MERSENNE PRIMES
      6. <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">F</i>((<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i>) = &#8721;) = ∑<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">f</i>((<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">d</i>) WHERE ) WHERE <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">d</i> IS A DIVISOR OF IS A DIVISOR OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i>
      7. THE MÖBIUS FUNCTION
      8. THE RIEMANN ZETA FUNCTION
      9. EXERCISES
    12. 7 THE EULER PHI FUNCTION
      1. THE <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">PHI</i> FUNCTION FUNCTION
      2. EULER’S GENERALIZATION OF FERMAT’S LITTLE THEOREM
      3. PHI OF A PRODUCT OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">m</i> AND AND <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i> WHEN WHEN <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">gcd</i>((<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">m</i>,,<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i>) &gt; 1) > 1
      4. THE ORDER OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">a</i> ( (<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">mod n</i>))
      5. PRIMITIVE ROOTS
      6. THE INDEX OF <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">m</i> ( (<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">mod p</i>) RELATIVE TO ) RELATIVE TO <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">a</i>
      7. TO BE OR NOT TO BE A QUADRATIC RESIDUE
      8. THE LEGENDRE SYMBOL
      9. QUADRATIC RECIPROCITY
      10. LAW OF QUADRATIC RECIPROCITY
      11. WHEN DOES <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">x</i><sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">2</sup> = = <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">a</i> ( (<i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">mod n</i>) HAVE A SOLUTION?) HAVE A SOLUTION?
      12. EXERCISES
    13. 8 SUMS AND PARTITIONS
      1. AN <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">n</i>TH POWER IS THE SUM OF TWO SQUARESTH POWER IS THE SUM OF TWO SQUARES
      2. SOLUTIONS TO THE DIOPHANTINE EQUATION <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">a</i><sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">2</sup> + + <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">b</i><sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">2</sup> + + <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">c</i><sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">2</sup> = = <i xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">d</i><sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0">2</sup>
      3. ROW SUMS OF A TRIANGULAR ARRAY OF CONSECUTIVE ODD NUMBERS
      4. PARTITIONS
      5. WHEN IS A NUMBER THE SUM OF TWO SQUARES?
      6. SUMS OF FOUR OR FEWER SQUARES
      7. EXERCISES
    14. 9 CRYPTOGRAPHY
      1. INTRODUCTION AND HISTORY
      2. PUBLIC-KEY CRYPTOGRAPHY
      3. FACTORING LARGE NUMBERS
      4. THE KNAPSACK PROBLEM
      5. SUPERINCREASING SEQUENCES
      6. EXERCISES
    15. ANSWERS OR HINTS TO SELECTED EXERCISES
      1. CHAPTER 1
      2. CHAPTER 2
      3. CHAPTER 3
      4. CHAPTER 4
      5. CHAPTER 5
      6. CHAPTER 6
      7. CHAPTER 7
      8. CHAPTER 8
      9. CHAPTER 9
    16. INDEX
    17. END USER LICENSE AGREEMENT