# Mathematics Courses

## Math 453: Elementary Theory of Numbers

### 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)

• 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