Mathematics 115
Fall, 2011
TuTh
9:40-11AM,
3 Evans Hall
Overview
This course is elementary in the sense that no
other upper-division course is needed as a prerequisite.
Although Math 53 and Math 54 are required of Math 115 students, Math 55 is
much more relevant. If you know abstract algebra (Math 113), then you
will find many arguments that are familiar from your study of groups
and rings. Whenever appropriate, I will allude to connections with
Math 113 for the benefit of those of you who have studied abstract algebra
or will do so at some point.
Textbook
An Introduction to the
Theory of Numbers, Fifth Edition
by
Ivan
Niven, H. S. Zuckerman and
Hugh L. Montomery.
Although the current edition
was published 20 years ago, this book remains one of the
definitive introductions to the subject. It is renowned for its
interesting, and sometimes challenging, problems.
Please see
Montgomery's
home page for the book and especially his lists of typos and errors
in the book. Note that there are multiple lists because the book has
been 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 used
repeatedly at Berkeley, most recently
one year ago.
Sage
Sage is a
free open-source mathematics software system
that does
number theory calculations that will illustrate
and conceivably even
illuminate the material of the course.
I urge you to become familiar with sage by taking
the tour
and then experimenting with the software.
I will try to assign interesting homework problems that require
sage (or other software) for calculations. I will also bring
sage into the classroom from time to time.
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.
Please do not plan travel on the dates of these exams.
If you believe that you have a conflicting obligation because of an
intercollegiate sport or other
extracurricular activity,
please read
these
guidelines
immediately.
For
practice exams, you might consult the web pages for my previous
Math 115 courses
and for
last
fall's course by
Martin Olsson.
You may also consult
Richard Borcherds's
Math 115
page for Fall, 2003.
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
Homework assignments will be due on Thursdays, with possible perturbations
because of midterm exams and the Thanksgiving holiday.
- 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.
- 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).
- 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
- 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.
- Assignment due September 29, 2011:
- §2.1, problem 50
- §2.2, problem 10
- §2.3, problems 9, 14, 18, 29, 33, 36, 40, 41
- Assignment due October 6, 2011.
- 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
- 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
- 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
- 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
- Assignment due November 10, 2011.
- Assignment due November 17, 2011.
- Assignment due November 22, 2011
(spoiler).
- 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
Course grades
will be based on a composite numerical score
that is intended to weight
the course components roughly as follows:
midterm exams 15% each, homework
25%, final exam 45%.
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
The calendar that follows (if you're logged into gmail!)
attempts to call your attention to "events" of interest to math 115 student:
class meetings, office hours, exams, noteworthy lectures (such as
the Serge
Lang undergraduate lecture by
Jordan Ellenberg,
which will be held on December 1 at 4:10PM.)
Now that the semester is over
The grades were distributed as follows:
11 As, 14 Bs, 4 Cs, 4 D/F. This rough
distribution ignores +'s and -'s and
does not reflect that some grades were converted to P or NP.
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: