Elementary Number Theory with Programming

Chapter 1: Special Numbers: Triangular, Oblong, Perfect, Deficient, and Abundant

• • Triangular Numbers
• • Oblong Numbers and Squares
• • Deficient, Abundant, and Perfect Numbers
• • Exercises

Chapter 2: Fibonacci Sequence, Primes, and the Pell Equation

• • Prime Numbers and Proof by Contradiction
• • Proof by Construction
• • Sums of Two Squares
• • Building a Proof on Prior Assertions
• • Sigma Notation
• • Some Sums
• • Finding Arithmetic Functions
• • Fibonacci Numbers
• • An Infinite Product
• • The Pell Equation
• • Goldbach’s Conjecture
• • Exercises

Chapter 3: Pascal’s Triangle

• • Factorials
• • The Combinatorial Numbers n Choose k
• • Pascal’s Triangle
• • Binomial Coefficients
• • Exercises

Chapter 4: Divisors and Prime Decomposition

• • Divisors
• • Greatest Common Divisor
• • Diophantine Equations
• • Least Common Multiple
• • Prime Decomposition
• • Semiprime Numbers
• • When is a Number an mth Power?
• • Twin Primes
• • Fermat Primes
• • Odd Primes Are Differences of Squares
• • When is n a Linear Combination of a and b?
• • Prime Decomposition of n!
• • No Nonconstant Polynomial with Integer Coefficients Assumes Only Prime Values
• • Exercises

Chapter 5: Modular Arithmetic

• • Congruence Classes Mod k
• • Laws of Modular Arithmetic
• • Modular Equations
• • Fermat’s Little Theorem
• • Multiplicative Inverses
• • Wilson’s Theorem
• • Wilson’s Theorem (2nd Version)
• • Squares and Quadratic Residues
• • Lagrange’s Theorem
• • Reduced Pythagorean Triples
• • Chinese Remainder Theorem
• • Exercises

Chapter 6: Number Theoretic Functions

• • The Tau Function
• • The Sigma Function
• • Multiplicative Functions
• • Perfect Numbers Revisited
• • Mersenne Primes
• • F(n) = Σf(d) Where d is a Divisor of n
• • The Möbius Function
• • The Riemann Zeta Function
• • Exercises

Chapter 7: The Euler Phi Function

• • The Phi Function
• • Euler’s Generalization of Fermat’s Little Theorem
• • Phi of a Product of m and n When gcd(m,n) > 1
• • The Order of a (mod n)
• • Primitive Roots
• • The Index of m (mod p) Relative to a
• • To Be or Not to Be a Quadratic Residue
• • The Legendre Symbol
• • Quadratic Reciprocity
• • Law of Quadratic Reciprocity
• • When Does x2 = a (mod n) Have a Solution?
• • Exercises

Chapter 8: Sums and Partitions

• • An nth Power is the Sum of Two Squares
• • Solutions to the Diophantine Equation a2 + b2 + c2 = d2
• • Row Sums of a Triangular Array of Consecutive Odd Numbers
• • Partitions
• • When is a Number the Sum of Two Squares?
• • Sums of Four or Fewer Squares
• • Exercises

Chapter 9: Cryptography

• • Introduction and History
• • Public-Key Cryptography
• • Factoring Large Numbers
• • The Knapsack Problem
• • Superincreasing Sequences
• • Exercises