Guide for the Instructor
This book is designed to be used as a text for a one-semester or full-year
course
in undergraduate number theory or for an independent study or reading course.
It contains approximately two semesters ’ worth of material, so the instructor of
a
one-semester course will have some flexibility in the choice of topics. The
first 11
chapters are basic, and probably most instructors will want to continue through
the RSA cryptosystem in Chapter 18, since in my experience this is one of the
students’ favorite topics.
There are now many ways to proceed. Here are a few possibilities that seem to
fit comfortably into one semester, but feel free to slice-and-dice the later
chapters
to fit your own tastes.
Chapters 20–32. Primitive roots, quadratic reciprocity, sums of squares,
Pell’s
equation, and Diophantine approximation. ( Add Chapters 39 and 40 on continued
fractions if time permits.)
Chapters 28–32 & 43–48. Fermat’s equation for exponent 4, Pell’s
equation, Diophantine
approximation, elliptic curves , and Fermat’s Last Theorem.
Chapters 29–37 & 39–40. Pell’s equation, Diophantine approximation,
Gaussian
integers transcendental numbers, binomial coefficients , linear recurrences ,
and continued fractions.
Chapters 19–25 & 36–38. Primality testing, primitive roots, quadratic
reciprocity,
binomial coefficients , linear recurrences , big-Oh notation. (This syllabus
is designed in particular for students planning further work in computer science
or cryptography.)
In any case, a good final project is to have the students read a few of the
omitted
chapters and do the exercises.
Most of the nonnumerical nonprogramming exercises in this book are designed
to foster discussion and experimentation. They do not necessarily have “correct”
or “complete” answers. Many students will find this extremely disconcerting at
first, so it must be stressed repeatedly. You can make your students feel more
at
ease by prefacing such questions with the phrase “Tell me as much as you can
about . . . .” Tell your students that accumulating data and solving special
cases are
not merely acceptable, but encouraged. On the other hand, tell them that there
is
no such thing as a complete solution, since the solution of a good problem
always
raises additional questions. So if they can fully answer the specific question
given
in the text, their next task is to look for generalizations and for limitations
on the
validity of their solution.
Aside from a few clearly marked exercises, calculus is required only in two late
chapters (Big-Oh notation in Chapter 38 and Generating Functions in Chapter 41).
If the class has not taken calculus, these chapters may be omitted with no harm
to
the flow of the material.
Number theory is not easy, so there’s no point in trying to convince the
students
that it is. Instead, this book will show your students that they are capable of
mastering a difficult subject and experiencing the intense satisfaction of
intellectual
discovery. Your reward as the instructor is to bask in the glow of their
endeavors.
Computers, Number Theory, and This Book
At this point I would like to say a few words about the use of computers in
conjunction
with this book. I neither expect nor desire that the reader make use of a
high-level computer package such as Maple, Mathematica , PARI, or Derive, and
most exercises (except as otherwised indicated) can be done with a simple pocket
calculator. To take a concrete example, studying greatest common divisors
(Chapter
5) by typing GCD[M,N] into a computer is akin to studying electronics by turning
on a television set. Admittedly, computers allow one to do examples with large
numbers, and you will find such computer-generated examples scattered through
the text, but our ultimate goal is always to understand concepts and
relationships.
So if I were forced to make a firm ruling, yea or nay, regarding computers, I
would
undoubtedly forbid their use.
However, just as with any good rule , certain exceptions will be admitted. First,
one of the best ways to understand a subject is to explain it to someone else,
so
if you know a little bit of how to write computer programs, you will find it
extremely
enlightening to explain to a computer how to perform the algorithms described
in this book. In other words, don’t rely on a canned computer package, do
the programming yourself. Good candidates for such treatment are the Euclidean
algorithm (Chapters 5–6) the RSA cryptosystem (Chapters 16–18), quadratic
reciprocity
(Chapter 25), writing numbers as sums of two squares (Chapters 26–27),
primality testing (Chapter 19), and generating rational points on elliptic
curves
(Chapter 43).
The second exception to the “no computer rule” is generation of data. Discovery
in number theory is usually based on experimentation, which may involve
examining reams of data to try to distinguish underlying patterns. Computers are
well suited to generating such data and also sometimes to assist in searching
for
patterns, and I have no objection to their being used for these purposes.
I have included a number of computer exercises and computer projects to
encourage
you to use computers properly as tools to help understand and investigate
the theory of numbers. Some of these exercises can be implemented on a small
computer (or even a programmable calculator ), while others require more
sophisticated
machines and/or programming languages. Exercises and projects requiring
a computer are marked by the symbol .
For many of the projects I have not given a precise formulation , since part of
the project is to decide exactly what the user should input and exactly what
form
the output should take. Note that a good computer program must include all the
following features:
• Clearly written documentation explaining what the program does, how to
use
it, what quantities it takes as input, and what quantities it returns as output.
• Extensive internal comments explaining how the program works.
• Complete error handling with informative error messages. For example, if
a = b = 0, then the gcd(a, b) routine should return the error message
“gcd(0,0) is undefined” instead of going into an infinite loop or
returning a “ division by zero ” error.
As you write your own programs, try to make them user friendly and as versatile
as possible, since ultimately you will want to link the pieces together to form
your
own package of number theoretic routines.
The moral is that computers are useful as a tool for experimentation and that
you can learn a lot by teaching a computer how to perform number theoretic
calculations,
but when you are first learning a subject, prepackaged computer programs
merely provide a crutch that prevent you from learning to walk on your own.
