Introduction to Number Theory (2024)

Fall, 2012
TuTh12:40-2PM,4 Evans Hall

Professor KennethA. Ribet email: Telephone: 510 642 0648 Fax: (510) 642-8204 Office hours(885EvansHall)

Overview

This course is elementary in the sense that nospecific courseis needed as a prerequisite.On the other hand,the abilityto read and write proofs is pretty much essential.Math 55 and Math 113 provide helpful background.As we encounter objects that can be regarded as groups, rings,fields, hom*omorphisms,..., I will mention the connectionto Math 113 in class.

Textbook

An Introduction to theTheory of Numbers, Fifth EditionbyIvanNiven, H. S. Zuckerman andHugh L. Montomery.Although the current editionwas published 20 years ago, this book remains one of thedefinitive introductions to the subject. It is renowned for itsinteresting, and sometimes challenging, problems.Please seeMontgomery'shome page for the book and especially his lists of typos and errorsin the book. Note that there are multiple lists because the book hasbeen reprinted several times.

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

Chapter-by-Chapter Description

• Chapter 1: Divisibility, the Euclidean algorithm,primes and the Fundamental Theorem of Arithmetic, proofs of theinfinitude of primes, the binomial theorem.Much of this material will be familiar from Math 55, but Ihope 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 theoremand its generalization by Euler,Wilson's theorem, Fermat's theorem characterizing integers thatare 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 residuesand 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 willallude to it from time to time, as I explained in connection withMath 113.
• Chapter 3: Quadratic reciprocity, the Jacobi symbol andapplications, binary quadratic forms.I hope to give several proofs of quadratic reciprocity, startingwith the proof in the book. This means, in particular, that I willbe lecturing on material not in the book.Similarly, when speaking about binary quadratic forms, I hope toexplain a new way of looking at the classical resultsthat was discovered recently byManjul 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 timeallows.For example, we will see in the beginning of the chapter thatthe Euclidean algorithm of chapter 1 is a method for finding thecontinued fraction expansion of a rational number.

Sage

Sage is afree open-source mathematics software systemthat doesnumber theory calculations that will illustrateandilluminate the material of the course.Even before the semester begins, you canbecome familiar with sage by takingthe tourand then experimenting with the software.When I taught Math 116 last semester,I projected a sage notebook from my laptop for a substantialfraction of each lecture period. Don't be surprised if Icontinue in that direction this semester.I will try to assign interesting homework problems that requiresage for calculations.

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

Examinations

• Firstmidterm exam, Thursday, September 20, 2012, in class(questions and skeletal solutions, mean 19.14, standard deviation 7.29).
• Lastmidterm exam, Thursday, October 25, 2012, in class(questions and skeletal solutions, mean 19.79, standarddeviation 7.55).
• Finalexamination, Friday, December 14, 2012, 8-11AM in3113Etcheverry Hall(questions and skeletal solutions).Onthis54-point exam, the mean was 34.26 while the standard deviation was 11.84.

Please do not plan travel on the dates of these exams.If you believe that you have a conflicting obligation because of anintercollegiate sport or otherextracurricular activity,please readtheseguidelinesimmediately.

Forpractice exams, you might consult the web pages for my previousMath 115 courses

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

and forarecent course byMartin Olsson.You may also consultRichard Borcherds'sMath 115page for Fall, 2003.

Grading

Course gradeswill be based on a composite numerical scorethat is intended to weight the course components roughly as follows:midterm exams 15% each, homework25%, final exam 45%.

When I taught this course in 2011, there were 33registered students. Grades were distributed as follows: 11 As,14 Bs, 4 Cs, 4 D/F. This rough distribution ignores +'s and -'s.Some students took the course P/NP. Their letter gradeswereconverted to P or NP when I entered the final grades.

For this course (Fall, 2012), there were 36 registered students. They received 17 As, 13 Bs, 3Cs and 3Fs.The students with the a P/NP grading option had their grades converted when final grades were entered.

You can look at thecourse evaluations that my Math 115students wrote in December, 2011 as well as theevaluations for this course.I encourage suggestions and comments about my teaching style and theevolution of the course. You can make them anonymously in various ways(e.g., by slipping a note under my office door) or just present themin email or a face-to-face conversation.

Homework

1. Assignment due August 30, 2012:§1.2, problems 1, 2 and 3: all parts, using sage;also problems 4b, 5, 7, 15, 25, 27, 28, 47
2. Assignment due September 6, 2012:§1.3, problems 2, 8, 10, 11, 13, 16, 17, 26, 28, 31
3. Assignment due September 13, 2012:
   • §1.3, problems 42, 44, 48(for the last problem, see the first linesof thebasic properties section of thewikipedia Fermatnumber entry)
   • §1.4, problems 3, 4
   • §2.1, problems 6, 13, 26, 30 (check using sage), 34, 35, 36, 37, 43
4. Assignment due September 20, 2012:
   • §1.2, problem 50
   • §1.3, problems 27, 29, 36
   • §1.4: Let n = 5k + j with k at least 1 and j = 0, 1, 2, 3 or 4.Show that k is congruent mod 5 to the binomial coefficient "n choose 5".
   • §2.1, problems 33, 40
   • §2.2, problems 8, 9
5. Assignment due September 29, 2012:§2.3, problems 4, 8, 13, 14, 17, 18, 26, 27, 29, 30, 39
6. Assignment due October 4, 2012:
   • §2.7, problems 1 (using sage if possible), 6, 12
   • §2.8, problems 3, 12, 16, 18, 20, 23
7. Assignment due October 11, 2012:
   • §2.8, problems 24, 25, 29, 30, 31
   • §2.9, problems 1ad, 7
   • §3.1, problems 4 (just use sage), 5 (use sage to compute), 6 (use sage to avoid tedium)
8. Assignment due October 18, 2012:
   • §3.1, problems 13, 14, 15, 16, 17, 18
   • §3.2, problems 6, 7, 8, 11, 13
9. Assignment due October 25, 2012:
   • §2.3, problem 37
   • §2.7, problems 13, 14
   • §2.8, problems 33, 34, 35
   • §3.3, problems 14, 15
10. Assignment due November 1, 2012:
    • §4.1, problems 2, 5, 9, 14, 17, 19, 34
    • §4.2, problems 10, 12, 16, 19
11. Assignment due November 8, 2012
12. Assignment due November 15, 2012:
    • §10.1, problems 3, 4
    • §10.2, problems 1, 2, 4, 5, 6
    • §10.3, problem 3
    • §10,4, problem 2
13. Assignment due November 27, 2012:
    • §5.4, problems 14
    • §5.6, problems 1, 9, 10 (skipping the part about "nonsingular")
    • §5.7, problems 9, 10
14. Assignment due December 6, 2012:
    • §2.4, problems 16, 17, 18
    • §5.8, problem 4
    • Find the order of the point P = (94269158776925 , 1102841572571055)on the elliptic curvedefined by y^2 = x^3 + 183821385707290x + 1153449657807210over the ring of integers modulo M=1636998688431221.Do this by using the elliptic curve factoring method to factorM; then use sage to compute the order of Pmodulo each of the factors of M.

Some web resources related to the course

• What is the smallestprime? byChris K. Caldwelland Yeng Xiong.
• Reinventing the Classroomby Harry R. Lewis.Should we organize Math 115 this way?
• The on-line encyclopedia of integersequences
• The prime pages
• Eckford Cohen's articleabout the prime factorization of n!, which includes a weird proof thatthere are infinitely many primes. (You have access to thefullarticle when authenticated as coming from Berkeley.)
• Acompendiumof proofs of Fermat's 1654 theorem to the effect that primes that are 1 mod 4are sums of two squares.See especiallyDon Zagier'sproofof the theorem.See also the PlanetMathaccountof the proof, which includes a simple proof of the uniqueness.
• While we're at it, you might enjoy Don Zagier's articleThefirst 50 million prime numbers
• A fairly old list ofalternativereferences for Math 115.
• An interesting and fairly recentdiscussionabout 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 is7, 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 theoriginal1872 manuscript by Zolotarev.In fact, you may find thismathoverflowdiscussion to be of great interest.One manuscript that mathoverflowrefers to is thisshortenedproof byWouter Castryck.
• Just to see if anyone is reading these links, here's anarticleabout a lecture that I gave on October 16, 2011 atHumboldt State University.I gave two more lectures the next day.
• Wikipedia'sdiscussionof the Lucas-Lehmer test.This web page was the basis for my lecture on November 3, 2011.
• William Stein's bookElementaryNumber Theory: Primes, Congruences, and Secrets.
• HenryCohen's articleA Short Proofof the Simple Continued Fraction Expansion of e.
• Hendrik Lenstra's2002 articleon Pell's equation.See alsoTheNumber of Real Quadratic Fields Having Units of Negative NormbyPeter Stevenhagen.

Calendar

The calendar that follows (at least if you're logged into gmail!)attempts to call your attention to "events" of interest to math 115 students:class meetings, office hours, exams, optional classget-togethers (coffee, lunch, breakfast), and special lectures forundergraduates.

Last Updated: