Instructor Dragos Oprea
Lectures: MWF 11:00-11:50AM, Cognitive Science Building 001
Course
Assistants		 Daniel Copeland
  • Discussion 1: Thursday, 9:00-9:50am in APM B412
  • Discussion 2: Thursday, 10-10:50 am in APM B412
  • Office: APM 6414
  • Office hour: Thursday 1-3.
  • Email: drcopela at ucsd dot edu
Course
Content		 Elementary number theory. Topics include unique factorization, residue systems, congruences, primitive roots, Diophantine equations.
Prerequisities: Math 31CH or Math 109, or consent of the instructor.
Grade
Breakdown 		The grade is computed as the following weighed average:

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

W. J. LeVeque, Fundamentals of Number Theory.
Readings

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

Homework problems will be assigned on the course homework page. There will be weekly problem sets, due Fridays at 4:30PM in the TA's mailbox (in the basement). 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. Recognizing that emergencies do happen, we will drop the lowest homework score.

Midterm
Exams

There will be two midterm exams given on April 29 and May 23. 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.
Final
Exam

The final examination will be held on Friday, June 19, 11:30 AM-2:30 AM. 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
  • Monday, March 28: First lecture
  • Friday, April 29: Midterm I
  • Monday, May 23: Midterm II
  • Monday, May 30: Memorial Day
  • Friday, June 3: Last Lecture
  • Friday, June 10: FINAL EXAM, 11:30 - 2:30.
Exams
Lecture Summaries
  • Lecture 1: Introduction. The integers. Well-ordered sets. Divisors. Division theorem and proof.
  • Lecture 2: Greatest common divisor -- definition and properties. The gcd is the smallest linear combination of the two integers. Euclidean algorithm for finding gcd.
  • Lecture 3: Prime numbers. Prime factorization: existence and uniqueness. Finding the gcd from prime factorization. Least common multiple.
  • Lecture 4: Solving linear diophantine equations.
  • Lecture 5: Euclidean domains. Norms. Divisibility, units, irreducible, primes. Primes implies irreducible. Existence of gcd, solvability of linear diophantine equations, unique factorization hold in an Euclidean domain.
  • Lecture 6: Examples of norms. In Euclidean domains, primes and irreducibles coincide. Example of domains with irreducible elements which are not prime. Gaussian integers form an Euclidean domain.
  • Lecture 7: Congruences. Congruence is an equivalence relation. The ring of integers modulo m and its operations. Examples, multiplication table. Investigation of the units in Z_m.
  • Lecture 8: More on the units in Z_m. Cancellation fails in Z_m in general. Finding inverses of units via Euclidean algorithm. Solving linear congruences.
  • Lecture 9: Multiplicative functions. Expression for Euler's function. Euler's function is multiplicative and strategy for the proof via Chinese remainder theorem.
  • Lecture 10: Proof of the Chinese remainder theorem. Solving linear systems of congruences and examples.
  • Lecture 11: General solutions to linear systems of congruences whose moduli are not coprime. Examples. Reduction of linear systems to "normal form".
  • Lecture 12: Solving higher degree congruences. Fermat and Euler's theorems. Reducing the degree of polynomial congruences. Other applications of Fermat and Euler.
  • Lecture 13: Complete and reduced residue systems. Proof of Fermat and Euler's theorems. Onto higher degree congruences. Statement of Lagrange's theorem.
  • Lecture 14: Lagrange's theorem about the number of solutions. Applications of Lagrange: the polynomial x^{p-1}-1 and Wilson's theorem. Quadratic and nonquadratic residues.
  • Lecture 15: More on quadratic residues. Legendre symbol and properties. -1 as a quadratic residue. Connection with Wilson's theorem.
  • Lecture 16: Primes and sum of two squares. Higher degree polynomial congruences modulo powers of primes. Taylor's theorem and constructing solutions inductively. Singular and non-singular solutions.
  • Lecture 16: More on Taylor's theorem. Examples of polynomial congruences modulo primes.
  • Lecture 17: Definition of primitive roots. Order of elements. Order divides the Euler function. Solving the discrete logarithm problem.
  • Lecture 18: Order of powers of elements in terms of order of the original element. Finding all primitive roots once we know a single one. Existence of primitive roots modulo a prime -- strategy for proof.
  • Lecture 19: Existence of primitive roots modulo primes - finished. Existence of primitive roots modulo squares of primes.
  • Lecture 20: Existence of primitive roots modulo powers of primes and twice powers of primes.
  • Lecture 21: Powers of 2 and non-existence of primitive roots. Generating the units modulo 2^e via signed powers of 5.
  • Lecture 22: Non-existence of primitive roots for moduli which are not 2, 4, p^e or 2p^e.
  • Lecture 23: Applications of primitive roots: quadratic and cubic residues modulo primes and powers of primes. nth residues.
  • Lecture 24: Solving the congruence x^n=a mod m. Number of solutions.
  • Lecture 25: More on Legendre symbol and its properties. Quadratic reciprocity and examples.