## Math 453: Elementary Theory of Numbers

Instructor 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.

- Kenneth Rosen,

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

Last modified by A.J. Hildebrand; approved by R. Muncaster