Instructor Dragos Oprea
Lectures: MWF 10:00-10:50AM, PETER 103
Artem Mavrin
  • Discussion 1: Monday, 7:00-7:50PM in B412
  • Discussion 2: Monday, 5-5:50p in APM 7421
  • Office: 6446
  • Office hour: Monday 3-4, 6-7; Tuesday 3-5
  • Email: amavrin at ucsd dot edu.
Elementary number theory. Topics include unique factorization, residue systems, congruences, primitive roots, reciprocity laws, quadratic forms, Diophantine equations.
Prerequisities: Math 31CH or Math 109, or consent of the instructor.
The grade is computed as the following weighed average:

  • Homework 20%, Midterm I 20%, Midterm II 20%, Final Exam 40%.

W. J. LeVeque, Fundamentals of Number Theory.


Reading the sections of the textbook corresponding to the assigned homework exercises is considered part of the homework assignment. You are responsible for material in the assigned reading whether or not it is discussed in the lecture. It will be expected that you read the assigned material in advance of each lecture.


Homework problems will be assigned on the course homework page. There will be 7 problem sets, due Wednesdays at 4:30PM in the TA's mailbox. You may work together with your classmates on your homework and/or ask the TA (or myself) for help on assigned homework problems. However, the work you turn in must be your own. No late homework assignments will be accepted.


There will be two midterm exams given on October 24 and November 21. There will be no makeup exams.

Regrading policy: graded exams will be handed back in section. Regrading is not possible after the exam leaves the room.


The final examination will be held on Friday, December 19, 8AM-11AM. There is no make up final examination. It is your responsability to ensure that you do not have a schedule conflict during the final examination; you should not enroll in this class if you cannot sit for the final examination at its scheduled time.

Announcements and Dates
  • Friday, October 3: First lecture
  • Friday, October 24: Midterm I
  • Tuesday, November 11: Veterans' Day.
  • Friday, November 21: Midterm II
  • Thursday-Friday, November 27-28: Thanksgiving. No class.
  • Friday, December 12: Last Lecture
  • Friday, December 19: FINAL EXAM, 8AM-11AM.
Lecture Summaries
  • Lecture 1: Introduction and motivation. Examples of problems addressed by number theory.
  • Lecture 2: Algebraic structures: monoids, groups, rings, domains, fields. Some examples. Gaussian integers, Eisenstein integers, quadratic integers.
  • Lecture 3: Subgroups. Subrings. Subfields. Homomorphism and isomomorphism. Ordered rings and well-ordering. Definition of the integers.
  • Lecture 4: Division theorem and proof. Divisibility and its properties. Greatest common divisor.
  • Lecture 5: Existence and uniqueness of the greatest common divisor. The gcd is expressed as a linear combination of the two numbers. Existence and uniqueness of the prime factorization.
  • Lecture 6: There are infinitely many primes. Computing the gcd and lcm from the prime factorization. Computing the gcd via Euclid's algorithm.
  • Lecture 7: Proof of Euclid's algorithm. Solving linear diophantine equations via Euclid's algorithm. General solution to linear diophantine equations.
  • Lecture 8: Euclidean algorithm in arbitrary domains implies existence of gcd, solvability of linear diophantine equations. Euclidean norms. Norms over quadratic integers. Gaussian integers form an Euclidean domain.
  • Lecture 9: Irreducible elements. Prime elements. Prime implies irreducible. Example of irreducible but not prime element in a domain. Unique factorization domains. In UFD, primes and irreducible coincide.
  • Lecture 10: Euclidean domains are unique factorization domains. Gaussian integers form a UFD.
  • Lecture 11: Congruences. Congruence is an equivalence relation. The ring of integers modulo m and its operations. Examples, multiplication table. Investigation of when Z_m is a domain, what the units are etc.
  • Lecture 12: The units in Z_m. Finding inverses of units via Euclidean algorithm. Euler's function. Multiplicative functions.
  • Lecture 13: Examples of multplicative functions: number of divisors, sum of divisors. The Euler function is multiplicative. Proof via the Chinese remainder theorem.
  • Lecture 14: Linear systems of congruences. Reduction to "normal form", finding solutions via the Chinese remainder theorem. Examples.
  • Lecture 15: General solutions to linear systems of congruences whose moduli are not coprime. Examples. Motivation for higher degree congruences and the need for further tools.
  • Lecture 16: Complete and reduced residue systems. Fermat and Euler's theorems. Proof. Examples. Reduction of degree of congruences via Fermat and Euler.
  • Lecture 17: Higher degree polynomial congruences. Lagrange's theorem about the number of solutions. Applications of Lagrange: the polynomial x^{p-1}-1 and Wilson's theorem; the polynomial x^{d}-1.
  • Lecture 18: Solving quadratic congruences. Quadratic residues and non-residues. Legendre symbol and properties.
  • Lecture 19: Higher degree polynomial congruences modulo powers of primes. Taylor's theorem and constructing solutions inductively. Singular and non-singular solutions.
  • Lecture 20: More on Taylor's theorem and examples. Midterm review.
  • Lecture 21: Primitive roots. Examples. Order of elements modulo m. Order divides the Euler function. Order of powers of elements in terms of order of the original element.
  • Lecture 22: Existence of primitive roots modulo a prime. There are exactly \phi(p-1) primitive roots modulo a prime. Finding all primitive roots once we know a single one. Generalizations modulo powers of a prime.
  • Lecture 23: Existence of primitive roots modulo squares of primes. Preparations for the existence of primitive roots modulo powers of odd primes.
  • Lecture 24: Existence of primitive roots modulo powers of odd primes. There are no primitive roots modulo powers of 2. Generating the units mod 2^e via signed powers of 5.
  • Lecture 25: Existence of primitive roots modulo 2p^e. Non existence of primitive roots for the remaining moduli. Examples.
  • Lecture 26: Applications of primitive roots. Solving exponential congruences using primitive roots. Listing quadratic, cubic residues using primitive roots.
  • Lecture 27: Solving the congruence x^n=a in Z_m using primitive roots. Number of solutions. Examples.