M328K (52890): Introduction to Number Theory

Place & Time: Fall 2019, Tuesday & Thursday 11:00 - 12:30 in RLM 5.114

Instructor: Florian Stecker, RLM 10.132, stecker@utexas.edu

Office hours: Tuesday 14:00 - 15:00 & Friday 10:00 - 11:00

Textbook: Elementary Number Theory and Its Applications, 6th edition, by Kenneth H. Rosen

Prerequisites: M341 or M325K, with a grade of at least C-.

Course contents: We will start with some basic properties of the integers and discuss how to prove things about them. Then we will talk about divisibility and prime numbers, and prove that every integer can be uniquely written as a product of prime numbers (the Fundamental Theorem of Arithmetic). After that we will introduce congruences, one of the main concepts of number theory, which will be the basis for the rest of the course. We will prove several well--known theorems about them, including the Chinese remainder theorem, Hensel's lemma, Wilson's theorem and Fermat's little theorem, and Euler's generalization of it. Then we will look at multiplicative arithmetic functions, most notably Euler's ϕ-function. We will discuss some applications of number theory, like checksums and public key cryptography. If time permits, we might also cover primitive roots and/or quadratic reciprocity.

Aug 29Axioms of the integers, Mathematical Induction, definition of divisibility
Sep 3Greatest common divisor, coprime integers, division with remainder, reduced fractions
Sep 5Greatest common divisors and linear combinations, Bezout's identity
Sep 10Linear Diophantine equations, Euclidean algorithm, extended Euclidean algorithm
Sep 12Prime numbers, sieve of Eratosthenes, infinitude of primes, Fundamental Theorem of Arithmetic
Sep 17Proof of the Fundamental Theorem, irrationality of roots of polynomials, gcd and lcm with prime factorizations
Sep 19Congruences, congruence classes, the definition of Z_m
Sep 24Addition and multiplication on Z_m, basic properties, modular exponentiation
Sep 26Solving linear equations in Z_m, Multiplicative inverses
Oct 3Check digits, ISBN-10
Oct 8ISBN-10, ISBN-13
Oct 10Map from Z_n to Z_m, Cartesian products, Chinese Remainder Theorem
Oct 15Constructive proof of CRT, Hensel's Lemma
Oct 17Proof of Hensel's Lemma & Example
Oct 22Wilson's Theorem
Oct 24Fermat's Little Theorem, Euler's Theorem, Phi-function
Oct 29Multiplicativity of the Phi-function
Nov 5Multiplicative functions, the number and sum of divisors
Nov 7Computing the number and sum of divisors, summatory function of phi
Nov 12Primitive roots, their basic properties
Nov 14Primitive roots mod primes and prime squares
Nov 19Primitive roots mod general integers
Nov 21Discrete logarithms, symmetric encryption
Nov 26Public-key encryption and signatures

Homework: Homework problems will be uploaded to the website every Thursday. Please hand in your solutions the following Thursday at the beginning of the lecture.

If the problem statement does not say otherwise, your task will always be to prove some statement. Note that writing proofs in a clear and understandable way is at least as important as having the right idea. A correct proof that is disorganized or inadequately justified will not receive full credit. You are encouraged to work with other students in the class, but solutions must be written up on an individual basis.

Homeworkdue dateremarks
Homework 1Sep 5
Homework 2Sep 12
Homework 3Sep 19Corrected version uploaded on Sep 14
Homework 4Sep 26For Problem 2 wait until Tuesday or guess what the multiplication operation might do. The rest is doable with what you know, but Tuesday's class might also be helpful for parts of Problem 5.
Homework 5Oct 3
Homework 6Oct 15
Homework 7Oct 22
Homework 8Oct 29
Homework 9Nov 7
Homework 10Nov 14changed the wording of Problem 3 slightly on Nov 10
Homework 11Nov 21
Homework 12Dec 3does not count towards the final grade

Exams: There will be three in-class midterm exams and one final exam. The lowest grade of the midterms will be dropped. All exams including the final take place in the usual room, RLM 5.114, but the final is at a different time and takes 3 hours.

Grading: The scores for your homework solutions will be added and rescaled to the range [0,20]. You will get up to 30 points for each of the midterm exams (with the lowest score being discarded), and up to 40 points for the final exam. The sum will determine your final grade in the following way:

108 - 120A
102 - 107A-
96 - 101B+
90 - 95B
84 - 89B-
78 - 83C+
72 - 77C
66 - 71C-
63 - 65D+
60 - 62D
57 - 59D-
0 - 56F

Students with disabilities: Students with disabilities may request appropriate academic accommodations from the Division of Diversity and Community Engagement (DDCE), Services for Students with Disabilities (SSD) at http://ddce.utexas.edu/disability