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.
Schedule:
| Aug 29 | Axioms of the integers, Mathematical Induction, definition of divisibility |
| Sep 3 | Greatest common divisor, coprime integers, division with remainder, reduced fractions |
| Sep 5 | Greatest common divisors and linear combinations, Bezout's identity |
| Sep 10 | Linear Diophantine equations, Euclidean algorithm, extended Euclidean algorithm |
| Sep 12 | Prime numbers, sieve of Eratosthenes, infinitude of primes, Fundamental Theorem of Arithmetic |
| Sep 17 | Proof of the Fundamental Theorem, irrationality of roots of polynomials, gcd and lcm with prime factorizations |
| Sep 19 | Congruences, congruence classes, the definition of Z_m |
| Sep 24 | Addition and multiplication on Z_m, basic properties, modular exponentiation |
| Sep 26 | Solving linear equations in Z_m, Multiplicative inverses |
| Oct 3 | Check digits, ISBN-10 |
| Oct 8 | ISBN-10, ISBN-13 |
| Oct 10 | Map from Z_n to Z_m, Cartesian products, Chinese Remainder Theorem |
| Oct 15 | Constructive proof of CRT, Hensel's Lemma |
| Oct 17 | Proof of Hensel's Lemma & Example |
| Oct 22 | Wilson's Theorem |
| Oct 24 | Fermat's Little Theorem, Euler's Theorem, Phi-function |
| Oct 29 | Multiplicativity of the Phi-function |
| Nov 5 | Multiplicative functions, the number and sum of divisors |
| Nov 7 | Computing the number and sum of divisors, summatory function of phi |
| Nov 12 | Primitive roots, their basic properties |
| Nov 14 | Primitive roots mod primes and prime squares |
| Nov 19 | Primitive roots mod general integers |
| Nov 21 | Discrete logarithms, symmetric encryption |
| Nov 26 | Public-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.
| Homework | due date | remarks |
| Homework 1 | Sep 5 | |
| Homework 2 | Sep 12 | |
| Homework 3 | Sep 19 | Corrected version uploaded on Sep 14 |
| Homework 4 | Sep 26 | For 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 5 | Oct 3 | |
| Homework 6 | Oct 15 | |
| Homework 7 | Oct 22 | |
| Homework 8 | Oct 29 | |
| Homework 9 | Nov 7 | |
| Homework 10 | Nov 14 | changed the wording of Problem 3 slightly on Nov 10 |
| Homework 11 | Nov 21 | |
| Homework 12 | Dec 3 | does 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 - 120 | A |
| 102 - 107 | A- |
| 96 - 101 | B+ |
| 90 - 95 | B |
| 84 - 89 | B- |
| 78 - 83 | C+ |
| 72 - 77 | C |
| 66 - 71 | C- |
| 63 - 65 | D+ |
| 60 - 62 | D |
| 57 - 59 | D- |
| 0 - 56 | F |
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