Introduction to Number Theory

Department: 
MATH
Course Number: 
4150
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Every spring semester

Primes and unique factorization, congruences, Chinese remainder theorem, Diophantine equations, Diophantine approximations, quadratic reciprocity. Applications such as fast multiplication, factorization and encryption.

Prerequisites: 

MATH 2406 or MATH 2106 or CS 3510 or CS 3511

Course Text: 

At the level of Elementary Number Theory and Its Applications, Kenneth H. Rosen, 5th ed. Pearson/Addison Wesley

Topic Outline: 
  • Prime numbers; sieve of Eratosthenes; unique factorization; congruence modulo n; Euclidean algorithm; Chinese Remainder Theorem
  • Arithmetic functions (\phi, \sigma, \mu, d); Fermat's (little Theorem); primitive roots; quadratic residues; reciprocity
  • Some elementary Diophantine equations (Pythagorean triples, sums of squares)
  • Primality testing; factorization; applications to cryptography