Mathematics 115

Fall, 2011
TuTh 9:40-11AM, 3 Evans Hall

Professor Kenneth A. Ribet email: Telephone: 510 642 0648 Fax: 510 642 8204

Overview

Textbook

This book is not cheap, but it should be easy to find used copies: “Niven & Zuckerman” (as the book is widely known) has been used repeatedly at Berkeley, most recently one year ago.

Sage

You can download the software for your Windows, Linux or MacOS X box. Alternatively, you can run sage online at http://www.sagenb.org/ after you create an account for yourself.

Examinations

• First midterm exam, Thursday, September 22, 2011, in class; maximum possible score = 45, mean = 26.8333, standard deviation = 8.03906.
• Last midterm exam, Thursday, October 27, 2011, in class; maximum possible score = 30, mean = 17.4375, standard deviation = 6.6281.
• Final examination, Tuesday, December 13, 2011, 3-6PM in 3 Evans; maximum possible score = 50, mean = 28.9, standard deviation = 10.32.

For practice exams, you might consult the web pages for my previous Math 115 courses

• Spring, 1998
• Fall, 1999
• Fall, 2000
• Fall, 2006

Chapter-by-Chapter Course Description

• Chapter 1: Divisibility, the Euclidean algorithm, primes and the Fundamental Theorem of Arithmetic, proofs of the infinitude of primes, the binomial theorem. Much of this material will be familiar from Math 55, but I hope that the book and my lectures will provide additional perspective. We can also do some computations with sage (see below).
• Chapter 2: Congruences, Euler's phi function, the ring of integers mod m, Fermat's little theorem and its generalization by Euler, Wilson's theorem, Fermat's theorem characterizing integers that are sums of two squares, polynomial equations mod m, the Chinese remainder theorem, Pollard's rho method for factoring, RSA cryptography, Hensel's lemma, primitive roots, quadratic residues and higher residues. This chapter ends with some material on groups, rings and fields. We will not discuss this material in any depth in class, but I will allude to it from time to time, as I explained in connection with Math 113.
• Chapter 3: Quadratic reciprocity, the Jacobi symbol and applications, binary quadratic forms. I hope to give several proofs of quadratic reciprocity, starting with the proof in the book. This means, in particular, that I will be lecturing on material not in the book. Similarly, when speaking about binary quadratic forms, I hope to explain a new way of looking at the classical results that was discovered recently by Manjul Bhargava.
• Chapter 4: Some functions of number theory. We will discuss only some of the material in this chapter. For example, we will prove the Moebius inversion formula.
• Chapter 7: We will discuss continued fractions, as time allows. For example, we will see in the beginning of the chapter that the Euclidean algorithm of chapter 1 is a method for finding the continued fraction expansion of a rational number.

Some web resources related to the course

• The on-line encyclopedia of integer sequences
• The prime pages
• Eckford Cohen's article about the prime factorization of n!, which includes a weird proof that there are infinitely many primes. (You have access to the full article when authenticated as coming from Berkeley.)
• A compendium of proofs of Fermat's 1654 theorem to the effect that primes that are 1 mod 4 are sums of two squares. See especially Don Zagier's proof of the theorem.
• While we're at it, you might enjoy Don Zagier's article The first 50 million prime numbers
• A fairly old list of alternative references for Math 115.
• An interesting and fairly recent discussion about the question of whether ((p-1)/2)! is +1 or -1 mod p when p is 3 mod 4. This residue class is 1 for p = 3, 23, 31, 59, 71 and 83 but -1 when p is 7, 11, 19, 43, 47, 67, 79. It's hard to see a pattern, isn't it?
• An alternative proof of the law of quadratic reciprocity. If you prefer, you can consult the original 1872 manuscript by Zolotarev. In fact, you may find this mathoverflow discussion to be of great interest. One manuscript that mathoverflow refers to is this shortened proof by Wouter Castryck.
• Just to see if anyone is reading these links, here's an article about a lecture that I gave on October 16 at Humboldt State University. I gave two more lectures the next day.
• Wikipedia's discussion of the Lucas-Lehmer test. This web page was the basis for my lecture on November 3, 2011.
• William Stein's book Elementary Number Theory: Primes, Congruences, and Secrets.
• Henry Cohen's article A Short Proof of the Simple Continued Fraction Expansion of e.
• Hendrik Lenstra's 2002 article on Pell's equation. See also The Number of Real Quadratic Fields Having Units of Negative Norm by Peter Stevenhagen.

Homework

1. Assignment due September 1, 2011. Assume in problem 19 that the set has at least two elements. The problem is visibly false for 1-element sets, even though the error hadn't been reported before.
2. Assignment due September 8, 2011:
   • §1.2, problems 50, 51, 52 (page 20);
   • §1.3, problems 8, 10, 16 (page 29); problems 26 and 31 (page 31).
3. Assignment due September 15, 2011:
   • §1.3, problems 41, 42, 44, 48;
   • §1.4, problems 2, 3 (all parts), 4 (all parts), 9, 11
   • §2.1, problems 5, 12, 15, 18
4. Assignment due September 22, 2011:
   • §1.4, problems 14, 15
   • §2.1, 48, 49, 50
   • §2.2, problems 4, 7, 8, 9, 10
   • §2.3, problems 2, 8. In addition, make up a Chinese Remainder Theorem problem that uses ridiculously large integers and then solve the problem using the crt command of sage.
5. Assignment due September 29, 2011:
   • §2.1, problem 50
   • §2.2, problem 10
   • §2.3, problems 9, 14, 18, 29, 33, 36, 40, 41
6. Assignment due October 6, 2011.
7. Assignment due October 13, 2011:
   • §2.6, problems 5, 7
   • §2.7, problems 2, 6, 11, 12, 13, 14
   • §2.8, problems 3, 8 (all parts), 9, 10, 11, 12, 13
8. Assignment due October 20, 2011:
   • §3.1, problems 6, 7 (all parts), 13, 14, 15, 16, 17, 21
   • §3.2, problems 4 (all parts), 5, 6, 7, 10
9. Assignment due October 27, 2011:
   • Use sage (or other means) to find all prime numbers p < 600 for which (p-1)! is congruent to -1 mod p^2.
   • §3.2, problems 11, 13, 15, 16, 18
   • §3.3, problems 1 (last two), 2 (all parts), 6, 7, 8, 13
10. Assignment due November 3, 2011:
    • §3.3, problems 14, 15, 16
    • §4.1, problems 1, 2, 5, 9
    • §4.2, problems 4, 12, 16, 19
11. Assignment due November 10, 2011.
12. Assignment due November 17, 2011.
13. Assignment due November 22, 2011 (spoiler).
14. Assignment due December 1, 2011:
    • §7.7, problems 1, 2
    • §7.8, problems 1, 2, 3, 4, 5, 6, 7, 10 (use sage as your "calculator" if possible)

Grading

When I last taught this course five years ago, there were 47 registered students at the end of the semester. One of the students had effectively dropped the course well before the final exam. The remaining 46 grades were distributed as follows: 17 As, 16 Bs, 13 Cs.

Calendar

Now that the semester is over

If you're a bit bored, you might enjoy gazing back at the class photo that we took right before the class ended. If you are totally bored, you can look at the course evaluations that were written around the same time.

Last Updated: