Requests for examination copies of the materials should go directly to the publisher. Visit this W.H. Freeman page and you should find a link which you can use to request a copy of the book.

W.H. Freeman is starting a web page with materials for the book. It is in the process of being updated.

Development of these course materials was supported by the NSF under grant Revitalizing Undergraduate Number Theory.

Course Basics

The basic operation of the course is as follows. (This is also explained in the first day handout below.)

• Each chapter starts with the pre-lab sheet. It contains background, exercises to be worked by hand, and may mention the larger questions which will be taken up in the computer lab. Each student turns in their individual answers to pre-lab questions the following class, which is . . .
• The next 2-3 classes are held in the lab. Students work through the lab notebooks in teams of two. Each notebook contains "Research questions" and "Exercises". Exercises are intended to be straightforward while research questions are not. Typically, the research questions will require experimentation, forming of conjectures, and proofs. We expect students to make varying degrees of progress on these questions.
• Then, there is 1 or 2 classes where teams of 2 pair up to make teams of 4. These groups compare notes and improve their results to produce a single report. The report should include conjectures formed with any progress on their resolution (counter-examples, partial proofs, complete proofs).
• After the reports are then turned in, the students receive a summary "wrap up" of what they might have found in the previous chapter. They also are assigned homework problems for the chapter

Version/Format Information

The Mathematica files require at least version 3.0.

Maple V worksheets require at least version R4. We also provide versions for R5, R5.1, and Maple 6.

Materials

The book, as purchased in the store contains an introduction to the course, all prelabs, all homework problems, a cd-rom with the electronic notebooks for Maple, Mathematica, and Web. The book also contains printouts of the electronic notebooks.

Now, here are the chapters and topics. Sections marked as Going Farther are expository (as opposed to discovery oriented). Some are in the lab, and some are in chapter summaries.

1. Divisibility and Factorization
   • Statement and use of unique factorization of integers
   • Introduction of greatest common divisors and the division algorithm
   • Number of divisors of an integer
   • Going Farther: sum of divisors of an integer
2. The Euclidean Algorithm and Linear Diophantine Equations
   • Euclidean algorithm
   • Integer solutions to ax+by=c
   • Going Farther: linear diophantine equations in 3 or more variables
   • Going Farther: proof of the fundamental theorem of arithmetic
3. Congruences
   • Introduction of congruences from several points of view (congruence classes, as remainders, and in terms of divisibility)
   • Well defined arithmetic mod m
   • Additive analog of Wilson's theorem
   • Additive orders
   • Going Farther: further analysis of additive orders leading to the formula for the sum of "phi(d)"
4. Applications of Congruences
   • Check digits (e.g., ISBN numbers)
   • Divisibility tests
   • Rock game (students have to think in terms of remainders or congruences to find the winning strategy to this game)
   • Going Farther: further analysis of divisibility tests
   • Going Farther (lab): Introduction to cryptography
   • Going Farther (lab): Shift ciphers
5. Solving Linear Congruences
   • Multiplicative inverses mod m
   • Solving ax congruent to b mod m in general
   • Wilson's theorem
   • Additive orders
   • Going Farther (lab): affine ciphers
   • Going Farther (lab): basic cryptanalysis
   • Going Farther: solving linear systems of congruences
6. Primes of Special Forms
   • Mersenne numbers
   • Connecting Mersenne primes with perfect numbers
   • Fermat numbers
   • Primes in arithmetic progressions
   • Going Farther: prime number theorem is introduced and used in a heuristic to predict whether there are a finite number or infinite number of Mersenne/Fermat primes
   • Going Farther: constructing regular polygons
7. Chinese Remainder Theorem
   • Standard chinese remainder theorem
   • Two CRT type congruences when the moduli may not be relatively prime
   • Explicit formulas for solving CRT
   • Going Farther: CRT as a bijective function
   • Going Farther: using the CRT for multi-precision computer arithmetic
8. Multiplicative Orders
   • Definition of (multiplicative) order of an integer modulo m
   • Limitations on orders
   • Fermat's little theorem and Euler's generalization
   • Going Farther: using Fermat's little theorem for compositeness testing
   • Going Farther: binary exponentiation algorithm
9. The Euler phi-function
   • Standard formula for computing the Euler phi-function
   • Going Farther (lab): RSA public key cryptosystem
   • Going Farther: Rabin-Miller compositeness test
10. Primitive Roots
    • Connecting multiplicative orders with additive orders
    • Definition and existence of primitive roots
    • All multiplicative orders in the presence of a primitive root
    • Going Farther (lab): discrete logarithms in cryptography (e.g., the Diffie-Hellman protocol)
    • Going Farther: explanation of part of the Pohlig-Hellman algorithm for computing discrete logarithms
    • Going Farther: proofs for primitive roots
11. Quadratic Congruences
    • Basics of quadratic residues/non-residues, Legendre symbol
    • Euler's criterion
    • Computing the Legendre symbol for 2 over p
    • Quadratic reciprocity
    • Going Farther: computing Legendre symbols quickly using the tools developed in the chapter
    • Going Farther: solution of a general quadratic congruence modulo an odd prime
12. Representation Problems
    • Representing integers as the difference of 2 squares
    • Representing integers as the sum of 2 squares
    • Pythagorean triples
    • Representing all integers as a sum of squares
    • Going Farther: Fermat's last theorem, proof for exponent 4
    • Going Farther: complete proof of Fermat's last theorem (just kidding)
13. Continued Fractions
    • Introduction of continued fractions as good rational approximations
    • Continued fraction expansions for square roots
    • x²-dy²=1