Instructor 
Dragos Oprea

Lectures: 
MWF 11:0011:50AM, Cognitive Science Building 001 
Course Assistants 
Daniel Copeland
 Discussion 1: Thursday, 9:009:50am
in APM B412
 Discussion 2: Thursday, 1010:50 am in APM B412
 Office: APM 6414
 Office
hour: Thursday 13.
 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 AM2: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 
 Preparation for Midterm 1:
 Preparation for Midterm 2:
 Preparation for Final Exam:

Lecture Summaries  
Lecture 1: Introduction. The integers. Wellordered 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^{p1}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 nonsingular
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 nonexistence of primitive roots.
Generating the units modulo 2^e via signed powers of 5.
 Lecture 22: Nonexistence 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.
