Math 115A, Number Theory

Fall 2019

Section 2: MWF 3:10-4:00PM, Hoagland 168

Welcome to the course webpage for Math 115A, Section 2. Here you will find some general info about the course. This is also the place to look for homework assignments, occasional course notes, and other things that might interest you.

Textbook TA and Discussion Homework Policy Exams Grading Homework Assignments Material by Day Various Notes Back to Main Page

ANNOUNCEMENT: The final for our class is on Thursday, 12/12, 3:30-5:30PM, in the usual classroom.

You will be allowed one side of a regular sheet of handwritten notes to bring to the final, but no calculators, books, other notes, phones, etc. Please do bring your student ID to the exam.

The exam will cover all of the material covered in class and on homework: it will be cumulative, with no intentional bias towards any particular part of the course.

Practice problems for the final are now available here. Solutions for these will be posted next week. We will have a review session for the final, time and place TBA.

ANNOUNCEMENT 2: There is no second midterm. However, I have put together a mock midterm 2 for you to test your knowledge of what you have been doing, from congruences through Fermat's Little Theorem. Treat it like you would an exam. Study for it, write up a half sheet cheat sheet just as for midterm 1, and then do the problems in 50 minutes with no books or notes or internet besides your cheat sheet. Solutions will be posted on Canvas. If you find that you really struggled on some topic, it may be good to come talk to me about it in office hours. The mock midterm is here.

Course Syllabus

Professor: Elena Fuchs
Office: 3109 Mathematical Sciences Bouilding
Email: efuchs at math dot ucdavis dot edu
Office hours: MW 10-11AM

Textbook and Prerequisites

The textbook this course is based on is Rosen's Elementary Number Theory and Its Applications, 6th Edition.

The prerequisite for this course is Math 21B. While the material in 21B itself is not a strict requirement, this course does expect that the students have some amount of mathematical maturity.

TA and Discussion:

The TA for our section is Matt Litman (mclitman at ucdavis dot edu). Starting the first week of class, he will hold discussion on Thursdays, 4:10-5PM in Olson 106. It is highly recommended that you attend these sections, in which you will see review of homework and more examples of topics covered in class.

Homeworks, Exams, and Grading:

Your grade for the course is determined as follows: 20% for homework, 35% for the midterm, and 45% for the final. There will be no make up exams.

Homework (along with occasional supplementary notes) will be posted here and will be due every Friday at 4:30PM in the appropriate homework box. Homework boxes re located in the Math Sciences Building: enter from the front, walk past the elevators and calculus room on your left and take a left turn where you will see many slots in the wall: find your section and slip in your homework. Please do not hand in your homework in class or via email, unless you have checked with me beforehand that this is ok. It should only be done in very special circumstances. You are encouraged to work with your classmates on homework and discuss the homework problems amongst each other. However, solutions should be written up independently, and you should write down which classmates you worked with at the top of your homework. The lowest homework score will be dropped. Therefore the policy is that no late homework will be accepted, especially since we will sometimes discuss the solutions to the homework problems in class.

The midterm will be in class on Monday, October 21st. More details about the exam will be announced in class and posted here closer to the date.

Sometime in November, I will also post a mock second midterm for you to try at home to test how well you have retained the material up to that point. Solutions will also be posted. Think of this as a useful studying tool and a way not to have to cram before the final.

If you have a cold or flu, I ask you to please do yourself, your classmates, me, and all the people we live with a huge favor by staying home and resting, rather than coming to class! If this happens, Matt and I will help you catch up on notes and things you missed in class once you are healthy!

Basic Plan:

We will cover parts of Rosen's Chapters 1, 3-6, and 8. Our goal, mathematically, is to understand divisibility, and how the divisors of a number effect various properties of it. We will then see some very interesting applications of this to cryptography (how information is encrypted when you, say, order something on Amazon). A broader goal of this course is to acquaint students with proofs: understanding them, writing them, and appreciating their importance.

Detailed Plan:

The following is a rough outline of what we will be doing in lecture every day, along with the relevant sections in the book (note that the reading for a given lecture should be taken to mean the relevant section of the mentioned chapter). In reality, we may move faster or slower. It will be updated on a regular basis.

9/25: Divisibility and primes. Working through examples involving induction proofs. Reading: section 1.5 and beginning of 3.1.
9/27: Cool facts about primes. Reading: 3.1 and 3.2.
9/30: More facts about primes, Sieve of Eratosthenes, gaps between primes. Reading: Section 3.1, 3.2.
10/2: Gaps between primes continued, greatest common divisors, Euclidean Algorithm. Reading: Section 3.2, 3.3, 3.4.
10/4: More on Euclidean Algorithm, the Fundamental Theorem of Arithmetic. Reading: Section 3.4, 3.5.
10/7: Finishing off Euclidean Algorithm and preparing for proof of the Fundamental Theorem of Arithmetic. Reading: Section 3.4, 3.5.
10/9: New definition of primes, proof of FTA. Reading: Section 3.5.
10/11: Finishing proof of the Fundamental Theorem of Arithmetic, going over least common multiples. Reading: Section 3.5.
10/14: Primes in arithmetic progressions. Reading: Section 3.5.
10/16: Congruences, beginning solving linear congruences. Reading: Section 4.1, 4.2, theorem 3.23 from Section 3.7.
10/18: Continuing with linear congruences. Reading: Section 4.2.
10/21: MIDTERM
10/23: Review of midterm. Solving linear congruences continued. Reading: Section 4.2.
10/25: Beginning Chinese Remainder Theorem. Reading: Section 4.3.
10/28: Chinese Remainder Theorem. Reading: Section 4.3.
10/30: Chinese Remainder Theorem, beginning Wilson's theorem. Reading: Section 4.3, 6.1.
11/1: Wilson's Theorem, beginning Fermat's LIttle Theorem. Reading: Section 6.1.
11/4: Fermat's Little Theorem, starting Euler's theorem. Reading: Section 6.1, 6.3.
11/6: Euler's Theorem and the Euler totient (phi) function. Reading: Section 6.3, 7.1.
11/8: Finishing off Euler's totient function. Reading: Section 7.1.
11/11: Veteran's Day: no class.
11/13: Finishing off discussion of Euler's totient function. RSA Cryptosystem. Reading: Sections 7.1, 8.4.
11/15: RSA Cryptosystem continued, possibly discussing some attacks against it. Reading: Section 8.4.
11/18: Finishing off RSA and attacks on RSA, beginning the Knapsack problem. Reading: Section 8.4, 8.5.
11/20: More on Knapsack problem, increasing sequences, and the Knapsack cryptosystem. Reading: Section 8.5.
11/22: Finishing Knapsack cryptosystem, beginning private key cryptosystems. Reading: Section 8.5, 8.1.
11/25: Frequency analysis, possibly beginning Diffie-Hellman Key Exchange. Reading: Section 8.1
11/27-11/29: No class due to Thanksgiving.

Some supplementary notes:

If you are new to writing proofs, here are some helpful free resources to guide you:
- How to write a solution to a problem by Art of Problem Solving. There are some good tips here, even if it is not specifically about proof writing. Reference provided by Laura Zehender of AoPS.
- A very good free online book on writing proofs by Ted Sundstrom, plus many screencasts (videos) by Robert Talbert to supplement it. Reference suggested by Dr. Rebecca Swanson of the Colorado School of Mines.
If you want further practice on number theory proofs, here are some resources available to you:
- Your book has plenty of exercises for each of the sections we covered, and most homework problems have not been out of the book.
- The UC Berkeley mathematics department has an archive of old exams for nearly all of their classes, including number theory (Math 115). The link to old number theory exams is here. Keep in mind that these exams are based on a semester course and cover more than we have in this class.
- Professor William Stein of the University of Washington has posted a free copy of his elementary number theory book on his website here. There are many relevant exercises in the first 3 chapters, although some that are based on material we have not seen in our course.
Further reading on Knapsack Cryptosystems, "The Rise and Fall of Knapsack Cryptosystems" by A.M. Odlyzko can be found here.
You can find a binary dictionary to use in Knapsack cipher problems here. The relevant part is the dictionary for capital letters.

Homework assignments:

Graded homework can be picked up in office hours or in class on Mondays. Graded midterms can be picked up in office hours.

Homework 1, due 10/4/2019
Homework 2 , due 10/11/2019

Homework 3 , due 10/18/2019. Note it is shorter than usual so that you have more time to prepare for the exam on 10/21.

Homework 4, due 10/28/2019. Note it is shorter than usual so that you have more time to prepare for the exam on 10/21.
Homework 5, due 11/1/2019.
Homework 6, due 11/8/2019.
Homework 7, due Friday, 11/15/2019.
Homework 8, due Friday, 11/22/2019.
Homework 9, due Friday, 12/6/2019.