Math 453: Elementary Theory of Numbers
Syllabus

Texts

• Text: James Strayer, Elementary Number Theory, Waveland Press, 1994/2002, ISBN 1-57766-224-5
• Alternate texts (available on library reserve):
  Kenneth Rosen, Elementary Number Theory and its Applications, 5th Edition, McGraw Hill, ISBN 0-201-87073-8.
  I. Niven, H. Zuckerman, H. Montgomery, An Introduction to the Theory of Numbers, 5th Edition, Wiley, ISBN 0471625469.

Sample Syllabus (based on Strayer)

• Chapter 1: Divisibility and Factorization (8 hours)
  • Divisibility: Definition, properties, division algorithm, greatest integer function
  • Primes: Definition, Euclid's Theorem, Prime Number Theorem (statement only), Goldbach and Twin Primes conjectures, Fermat primes, Mersenne primes
  • The greatest common divisor: Definition, properties, Euclid's algorithm, linear combinations and the gcd
  • The least common multiple: Definition and properties,
  • The Fundamental Theorem of Arithmetic: Euclid's Lemma, canonical prime factorization, divisibility, gcd, and lcm in terms of prime factorizations
  • Primes in arithmetic progressions: Dirichlet's Theorem on primes in arithmetic progressions (statement only)
• Chapter 2: Congruences (8 hours)
  • Definitions and basic properties, residue classes, complete residue systems, reduced residue systems
  • Linear congruences in one variable, Euclid's algorithm
  • Simultaneous linear congruences, Chinese Remainder Theorem
  • Wilson's Theorem
  • Fermat's Theorem, pseudoprimes and Carmichael numbers
  • Euler's Theorem
• Chapter 3: Arithmetic functions (8 hours)
  • Arithmetic function, multiplicative functions: definitions and basic examples
  • The Moebius function, Moebius inversion formula
  • The Euler phi function, Carmichael conjecture
  • The number-of-divisors and sum-of-divisors functions
  • Perfect numbers, characterization of even perfect numbers
• Chapter 4: Quadratic residues (4 - 6 hours)
  • Quadratic residues and nonresidues
  • The Legendre symbol: Definition and basic properties, Euler's Criterion, Gauss' Lemma
  • The law of quadratic reciprocity
• Chapter 5: Primitive roots (4 - 6 hours)
  • The order of an integer
  • Primitive roots: Definition and properties,
  • The Primitive Root Theorem: Characterization of integers for which a primitive root exists
• Additional Topics (8 - 12 hours): Selected from Chapters 6 - 8 of Strayer, or other sources. Possible choices include:
  • Continued fractions and rational approximations
  • Sums of squares
  • Pythagorean triples
  • Pell's equation
  • Partitions
  • Recurrences
  • Applications to primality testing
  • Application to cryptography