Preface

This is a textbook about prime numbers, congruences, basic public-key cryptography, quadratic reciprocity, continued fractions, elliptic curves, and number theory algorithms. We will mention groups, rings, and fields in passing at various places in this book, but much of the book should be comprehensible without a course in algebra. This book grew out of an undergraduate course that the author taught at Harvard University in 2001 and 2002, at UC San Diego in 2005, and at University of Washington in 2007.

Notation and Conventions. We let $\mathbb {N}=\{1,2,3,\ldots\}$ denote the natural numbers, and use the standard notation $\mathbb {Z}$ , $\mathbb {Q}$ , $\mathbb {R}$ , and $\mathbb {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.6. Seth Kleinerman wrote a version of Section 5.3 as a class project. Samit Dasgupta, George Stephanides, Kevin Stern, Ting-You Wang, and Heidi Williams all suggested corrections. I also benefited from conversations with Henry Cohn and David Savitt. I used SAGE, emacs, and L^ATEX in the preparation of this book.

Numerous mistakes and typos corrected by: Arthur Patterson, Eve Thompson