Math 126: Theory of numbers

MacQuarrie Hall 233, MW noon-1:15pm (Sec. 01, code 28868)

Last update of this page: Tue May 12, 2015

Announcements:

• Homework for this class can be submitted either in person or online. If you want to submit a homework assignment online, please submit it via Canvas, which you probably know how to use better than I do. (If you don't, check out the tutorials here; the only part of Canvas we will use is online assignment submission.) If Canvas doesn't know that you're enrolled in this course, please email me at tim.hsu@sjsu.edu, and I'll make that happen ASAP.

  If you submit homework online, please use the following filename convention. (The convention is shown here for a student named Sarah Jane Smith doing PS01 and submitting in pdf format; please substitute your own name, PSxx, and your file format as appropriate.)

  • Outline: PS01-outline-Smith.pdf
  • Complete PS01: PS01-Smith.pdf
  • Revision number 1: PS01-rev1-Smith.pdf (and similarly for further revisions)
  
  If there's more than one Smith in the class, I'll let you know, and you can use something like PS01-Smith-SJ.pdf.

• If you're interested in typesetting math, the system I use to make my handouts is called LaTeX, and it can be downloaded for free (in Windows format) at http://www.miktex.org. If you own a Mac (system OS X) or a Linux computer, you already own a copy of this program, as it's been a standard Unix program for about 20 years. And for our purposes, the key point is that under any system, LaTeX can produce pdf output that is ideal for online homework submission.
  LaTeX is well worth learning, if you have some free time; it's used for manuals and technical reports throughout nerd-dom. For self-study, I highly recommend the LaTeX book by Leslie Lamport, which you can purchase here.
• Maple worksheets and other computer demos used in class:
  • A few terms of the sequence that appears implicitly in Euclid's proof that there are infinitely many primes
  • Some experiments about the distribution of the primes (how many, residues (mod m), etc.)
  • Some experiments about Mersenne primes and Fermat primes
  • Snapshot of a successive squaring algorithm for computing a^k (mod m)
  • Examples of a "Fermat" primality test and the Rabin-Miller test

FUA (Frequently Used Acronyms):

Administrative handouts:

Course notes:

Background: Writing proofs.

Supplemental material: None yet.

Data: The first 500 primes, in text, Excel spreadsheet, and csv formats.

Number theory online: Indexed by related chapter in the text.

• Website for A Friendly Introduction to Number Theory, maintained by the author.
• (Ch. 12) The article Prime number races, which gives an even more detailed examination of what happens with Dirichlet's Theorem on Primes in Arithmetic Progressions. Fun and accessible, with ideas for student research projects.
• (Ch. 13) Not mentioned in this chapter, but another phenomenon along the same lines: Bertrand's postulate: For n > 1, there is always a prime p such that n < p < 2n.
• (Ch. 13) The Twin Prime Conjecture Song (from the PBS show NOVA), on the 2005 work of SJSU's own Dan Goldston (with Janos Pintz and Cem Yildirim). You can also read a technical description here, though after the first 2 pages or so, it's only accessible to people with Ph.D.'s in math.
• (Ch. 13) In a manner typical of modern math, the work of Goldston-Pintz-Yildirim led in an unexpected way to recent work by Ben Green (who spoke in the SJSU Math Colloquium in 2008) and Terence Tao proving that primes exist in arbitrarily long arithmetic progressions.
  • For a guide to the Green-Tao theorem, start with these slides (July 19, 2009) from Tao's blog.
  • Andrew Granville's paper on prime number patterns is another accessible account of the Green-Tao theorem and many wonderful consequences that follow from it.
  • For technical details, Tao's number theory page has pretty much everything you could ever want to know on this topic.
• (Ch. 13) Then in 2013, a little-known mathematician named Yitang Zhang proved that there are infinitely many primes with gap size at most 70,000,000 (or so). Here is a description of what Zhang did, and here's a documentary about Zhang.
• (Ch. 13) Subsequently, various mathematicians worked on reducing the gap size of 70,000,000, above, as much as possible. This effort culminated in the 2014 with a paper by the polymath project (i.e., a "crowdsourced" group of mathematicians working together), proving that the "lower bound" gap size is at most 246. See the results of the polymath project here.
• (Ch. 12-13) The Prime Pages (references and resources about prime numbers).
• (Ch. 14) The Great Internet Mersenne Prime Search.
• (Ch. 14) Richard Guy's award-winning article The Strong Law of Small Numbers, on patterns that work for a while and then stop, and a few that go on forever. Many such patterns involve primes.
• (Ch. 19) For more on the proof that there are infinitely many Carmichael numbers, see this blog post or the original paper itself.
• (Ch. 19) One notable and relatively recent development in primality testing is the AKS primality test, which is notable both because it is the first "practical" (polynomial running time) primality test that does not rely on randomness/guessing, and also because two of its co-creators were undergraduate students at the time (Neeraj Kayal and Nitin Saxena, supervised by Manindra Agrawal). For a brief description of the test and the hoopla surrounding its discovery, see this article from the Notices of the AMS. In fact, you can read the paper itself here (it's surprisingly readable).
• (Ch. 22) Franz Lemmermeyer maintains an online chronology and bibliography describing (as of Apr 2015) 246 published proofs of quadratic reciprocity. (Amazingly, the list is not complete, and more are being produced; for example, proofs 244 and 246 were discovered or published in 2013.)

Topics for exams:

Sample exams:

Problem sets:

HW	Outline due	Due date	Last revision due	Problems
PS01	Fri Jan 30	Mon Feb 02	Mon Feb 16	1.1, 1.3, 1.4, 2.2, 2.6, 3.2.
PS02	Fri Feb 06	Mon Feb 09	Mon Mar 16	5.1, 5.4, 6.1(a), 6.2(c), 6.4, 6.5.
PS03	Fri Feb 13	Mon Feb 16	Mon Mar 30	7.1, 7.6, 8.1(a), 8.2, 8.3(b,d), 8.4(a,d), 8.5(a,b).
PS04	Fri Feb 27	Mon Mar 02	Mon Apr 20	8.9, 9.1(a,c), 9.2, 9.4(a,c), 10.2, 11.1, 11.2.
PS05	Fri Mar 06	Mon Mar 09	Mon Apr 20	11.3, 11.7, 11.10, 11.11(b,c), 12.2, 12.4, 13.5.
PS06	Fri Mar 13	Mon Mar 16	Wed May 13	13.6, 14.3(a,b,c), 15.1, 15.2, 15.3, 15.5, 15.8(a,b).
PS07	Fri Apr 03	Mon Apr 06	Wed May 13	See handout (revised Mar 31).
PS08	Fri Apr 10	Mon Apr 13	Wed May 13	19.1(a), 19.4(a), 19.7(a,b), 20.1, 20.2(a-d), (20.3).
PS09	Fri Apr 17	Mon Apr 20	Wed May 13	21.1(b,d), 21.2, 21.3, 21.4, 22.1(b,d), 22.3.
PS10	Fri May 01	Mon May 04	TBA	22.6, 22.7, 22.10, 24.1(b), 24.4(b), 24.6(a,b).
PS11	Fri May 08	Mon May 11	TBA	25.1(a,d), 25.4, 31.1, 32.3. (DELETED: 31.3, 32.1.)

Reading assigned in course:

• Instructor: Tim Hsu.
• Required text: A Friendly Introduction to Number Theory, Joseph H. Silverman, 4th ed., 2013 (prime number rotors on cover)
• Homework: Outline and final version due once each week, except in exam weeks. For details, see the handout on homework in Math 126.
• Exams: Three in-class 75-minute exams, plus 2 hour, 15 min final exam (Thu May 21, 9:45am-noon).
• Grading: Final course grades consist of:
  

  Homework:	20%
  Exam 1:	14%
  Exams 2 & 3:	18% each
  Final:	30%