Preface
The 1990s saw a wave of calculus reform whose aim was to teach students to think
for themselves and to solve substantial problems, rather than merely memorizing
formulas and performing rote algebraic manipulations. This book has a similar,
albeit somewhat more ambitious, goal, to lead you to think mathematically and
to experience the thrill of independent intellectual discovery. Our chosen
subject,
Number Theory , is particularly well suited for this purpose. The natural numbers
1, 2, 3, . . . satisfy a multitude of beautiful patterns and relationships, many
of
which can be discerned at a glance, others are so subtle that one marvels they
were
noticed at all. Experimentation requires nothing more than paper and pencil, but
many false alleys beckon to those who make conjectures on too scanty evidence.
It
is only by rigorous demonstration that one is finally convinced that the
numerical
evidence reflects a universal truth. This book will lead you through the groves
wherein lurk some of the brightest flowers of Number Theory, as it
simultaneously
encourages you to investigate, analyze, conjecture, and ultimately prove your
own
beautiful number theoretic results.
This book was originally written to serve as a text for Math 42, a course
created
by Jeff Hoffstein at Brown University in the early 1990s. Math 42 was designed
to
attract nonscience majors, those with little interest in pursuing the standard
calculus
sequence, and to convince them to study some college mathematics. The intent was
to create a course similar to one on, say, “The Music of Mozart” or “Elizabethan
Drama,” wherein an audience is introduced to the overall themes and methodology
of an entire discipline through the detailed study of a particular facet of the
subject.
Math 42 has been extremely successful, attracting both its intended audience and
also scientifically oriented undergraduates interested in a change of pace from
their
large-lecture, cookbook-style courses.
The prerequisites for reading this book are few. Some facility with high school
algebra is required , and those who know how to program a computer will have fun
generating reams of data and implementing assorted algorithms, but in truth the
reader needs nothing more than a simple calculator . Concepts from calculus are
mentioned in passing, but are not used in an essential way. However, and the
reader
is hereby forewarned, it is not possible to truly appreciate Number Theory
without
an eager and questioning mind and a spirit that is not afraid to experiment, to
make
mistakes and profit from them, to accept frustration and persevere to the
ultimate
triumph. Readers who are able to cultivate these qualities will find themselves
richly rewarded, both in their study of Number Theory and their appreciation of
all
that life has to offer.
Acknowledgments for the First Edition
There are many people I would like to thank for their assistance—Jeff Hoffstein,
Karen Bender, and Rachel Pries for their pioneering work in Math 42, Bill Amend
for kindly permitting me to use some of his wonderful FoxTrot cartoons, the
creators
of PARI for providing the ultimate in number theory computational power ,
Nick Fiori, Daniel Goldston, Rob Gross, Matt Holford, Alan Landman, Paul
Lockhart,
Matt Marcy, Patricia Pacelli, Rachel Pries (again), Michael Schlessinger,
Thomas Shemanske, Jeffrey Stopple, Chris Towse, Roger Ware, Larry Washington,
Yangbo Ye, and Karl Zimmerman for looking at the initial draft and offering
invaluable suggestions, Michael Artin, Richard Guy, Marc Hindry, Mike Rosen,
Karl Rubin, Ed Scheinerman, John Selfridge, and Sam Wagstaff for much helpful
advice, and George Lobell and Gale Epps at Prentice Hall for their excellent
advice
and guidance during the publication process.
Finally, and most important, I want to thank my wife Susan and children Debby,
Daniel, and Jonathan for their patience and understanding while this book was
being written.
Acknowledgments for the Second Edition
I would like to thank all those who took the time to send me corrections and
suggestions
that were invaluable in preparing this second edition, including Arthur Baragar,
Aaron Bertram, Nigel Boston, David Boyd, Seth Braver, Michael Catalano-
Johnson, L. Chang, Robin Chapman, Miguel Cordero, John Cremona, Jim Delany,
Lisa Fastenberg, Nicholas Fiori, Fumiyasu Funami, Jim Funderburk, Andrew
Granville, Rob Gross, Shamita Dutta Gupta, Tom Hagedorn, Ron Jacobowitz, Jerry
S. Kelly, Hershy Kisilevsky, Hendrik Lenstra, Gordon S. Lessells, Ken Levasseur,
Stephen Lichtenbaum , Nidia Lopez Jerry Metzger, Jukka Pihko, Carl Pomerance,
Rachel Pries, Ken Ribet, John Robeson, David Rohrlich, Daniel Silverman, Alfred
Tang, and Wenchao Zhou.
Acknowledgments for the Third Edition
I would like to thank Jiro Suzuki for his beautiful translation of my book into
Japanese. I would also like to thank all those who took the time to send me
corrections
and suggestions that were invaluable in preparing this third edition, including
Bill Adams, Autumn Alden, Robert Altshuler, Avner Ash, Joe Auslander,
Dave Benoit, J¨urgen Bierbrauer, Andrew Clifford, Keith Conrad, Sarah DeGooyer,
Amartya Kumar Dutta, Laurie Fanning, Benji Fisher, Joe Fisher, Jon Graff, Eric
Gutman, Edward Hinson, Bruce Hugo, Ole Jensen, Peter Kahn, Avinash Kalra,
Jerry Kelly, Yukio Kikuchi, Amartya Kumar, Andrew Lenard, Sufatrio Liu, Troy
Madsen, Russ Mann, Gordon Mason, Farley Mawyer, Mike McConnell, Jerry
Metzger, Steve Paik, Nicole Perez, Dinakar Ramakrishnan, Cecil Rousseau, Marc
Roth, Ehud Schreiber, Tamina Stephenson, Jiro Suzuki, James Tanton, James Tong,
Chris Towse, Roger Turton, Fernando Villegas, and Chung Yi.
Email and Electronic Resources
All the people listed above have helped me to correct numerous mistakes and to
greatly refine the exposition, but no book is ever free from error or incapable
of
being improved. I would be delighted to receive comments, good or bad, and
corrections from my readers.
Introduction
Euclid alone
Has looked on Beauty bare. Fortunate they
Who, though once only and then but far away,
Have heard her massive sandal set on stone.
Edna St. Vincent Millay (1923)
The origins of the natural numbers 1, 2, 3, 4, 5, 6, . . . are lost in the mists
of
time. We have no knowledge of who first realized that there is a certain concept
of
“threeness” that applies equally well to three rocks, three stars, and three
people.
From the very beginnings of recorded history, numbers have inspired an endless
fascination—mystical, aesthetic, and practical as well. It is not just the
numbers
themselves, of course, that command attention. Far more intriguing are the
relationships
that numbers exhibit, one with another. It is within these profound and
often subtle relationships that one finds the Beauty so strikingly described in
Edna
St. Vincent Millay’s poem. Here is another description by a celebrated
twentieth-century
philosopher.
Mathematics, rightly viewed, possesses not only truth, but supreme
beauty—a beauty cold and austere, like that of sculpture, without appeal
to any part of our weaker nature, without the gorgeous trappings
of paintings or music, yet sublimely pure, and capable of a stern perfection
such as only the greatest art can show. (Bertrand Russell, 1902)
The Theory of Numbers is that area of mathematics whose aim is to uncover
the many deep and subtle relationships between different sorts of numbers. To
take
a simple example, many people through the ages have been intrigued by the square
numbers 1, 4, 9, 16, 25, . . . . If we perform the experiment of adding together
pairs
of square numbers, we will find that occasionally we get another square. The
most
famous example of this phenomenon is
but there are many others, such as
Triples like (3, 4, 5), (5, 12, 13), (20, 21, 29), and
(28, 45, 53) have been given the
name Pythagorean triples. Based on this experiment, anyone with a lively
curiosity
is bound to pose various questions, such as “Are there infinitely many
Pythagorean
triples?” and “If so, can we find a formula that describes all of them?” These
are the sorts of questions dealt with by number theory.
As another example, consider the problem of finding the remainder when the
huge number
is divided by 54817263. Here’s one way to solve this
problem. Take the number
32478543, multiply it by itself 743921429837645 times, use long division to
divide
by 54817263, and take the remainder. In principle, this method will work,
but in practice it would take far longer than a lifetime, even on the world’s
fastest
computers. Number theory provides a means for solving this problem, too. “Wait a
minute,” I hear you say, “Pythagorean triples have a certain elegance that is
pleasing
to the eye, but where is the beauty in long division and remainders?” The
answer is not in the remainders themselves, but in the use to which such
remainders
can be put. In a striking turn of events, mathematicians have shown how the
solution of this elementary remainder problem (and its inverse) leads to the
creation
of simple codes that are so secure that even the National Security Agency
is unable to break them. So much for G.H. Hardy’s singularly unprophetic remark
that “no one has yet discovered any warlike purpose to be served by the theory
of
numbers or relativity, and it seems very unlikely that anyone will do so for
many
years.”
The land of Number Theory is populated by a variety of exotic flora and fauna.
There are square numbers and prime numbers and odd numbers and perfect numbers
(but no square-prime numbers and, as far as anyone knows, no odd-perfect
numbers). There are Fermat equations and Pell equations, Pythagorean triples and
elliptic curves, Fibonacci’s rabbits, unbreakable codes, and much, much more.
You
will meet all these creatures, and many others, as we journey through the Theory
of Numbers.
