Elementary Number Theory: Primes, Congruences, and Secrets

This is a book about prime numbers, congruences, secret messages, and elliptic curves that you can read cover to cover. It grew out of undergraduate courses that the author taught at Harvard, UC San Diego, and the University of Washington.

The systematic study of number theory was initiated around 300B.C. when Euclid proved that there are infinitely many prime numbers, and also cleverly deduced the fundamental theorem of arithmetic, which asserts that every positive integer factors uniquely as a product of primes. Over a thousand years later (around 972A.D.) Arab mathematicians formulated the congruent number problem that asks for a way to decide whether or not a given positive integer n is the area of a right triangle, all three of whose sides are rational numbers.

Then another thousand years later (in 1976), Diffie and Hellman introduced the first ever public-key cryptosystem, which enabled two people to communicate secretely over a public communications channel with no predetermined secret; this invention and the ones that followed it revolutionized the world of digital communication. In the 1980s and 1990s, elliptic curves revolutionized number theory, providing striking new insights into the congruent number problem, primality testing, publickey cryptography, attacks on public-key systems, and playing a central role in Andrew Wiles’ resolution of Fermat’s Last Theorem.

Today, pure and applied number theory is an exciting mix of simultaneously broad and deep theory, which is constantly informed and motivated by algorithms and explicit computation. Active research is underway that promises to resolve the congruent number problem, deepen our understanding into the structure of prime numbers, and both challenge and improve our ability to communicate securely. The goal of this book is to bring the reader closer to this world.

The reader is strongly encouraged to do every exercise in this book, checking their answers in the back (where many, but not all, solutions are given). Also, throughout the text there, are examples of calculations done using the powerful free open source mathematical software system Sage (http://www.sagemath.org), and the reader should try every such example and experiment with similar examples.