Elementary Number Theory - William Stein.pdf

This is a textbook about prime numbers, congruences, basic public-key
cryptography, quadratic reciprocity, continued fractions, elliptic curves, and
number theory algorithms. We assume the reader has some familiarity with
groups, rings, and ¯elds, and for Chapter 7 some programming experience.
This book grew out of an undergraduate course that the author taught at
Harvard University in 2001 and 2002.


Notation and Conventions. We let N = f1; 2; 3; : : :g denote the natural
numbers, and use the standard notation Z, Q, R, and C for the rings of
integer, rational, real, and complex numbers, respectively. In this book we
will use the words proposition, theorem, lemma, and corollary as follows.
Usually a proposition is a less important or less fundamental assertion, a
theorem a deeper culmination of ideas, a lemma something that we will
use later in this book to prove a proposition or theorem, and a corollary
an easy consequence of a proposition, theorem, or lemma.
Acknowledgements. Brian Conrad and Ken Ribet made a large number
of clarifying comments and suggestions throughout the book. Baurzhan
Bektemirov, Lawrence Cabusora, and Keith Conrad read drafts of this book
and made many comments. Frank Calegari used the course when teaching
Math 124 at Harvard, and he and his students provided much feedback.
Noam Elkies made comments and suggested Exercise 4.5. Seth Kleinerman
wrote a version of Section 5.3 as a class project. Samit Dasgupta, George
Stephanides, Kevin Stern, and Heidi Williams all suggested corrections.