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

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.

Office: 3109 Mathematical Sciences Bouilding

Email: efuchs at math dot ucdavis dot edu

Office hours: MW 10-11AM

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.

The TA for our section is Matt Litman (mclitman at ucdavis dot edu). Starting the

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.

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.

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.

- 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 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.