A Friendly Introduction to Number Theory

This page contains the following material from A Friendly Introduction to Number Theory.

Return to Friendly Introduction... Home Page

Preface

 The 1990's have seen a wave of calculus reform whose aim is to teach students to think for themselves and to solve substantial problems, rather than merely to memorize formulas and perform rote algebraic manipulations. This book has a similar, albeit somewhat more ambitious, goal, namely to lead students 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 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 scanty evidence. It is only by rigorous demonstration that one is finally convinced that the numerical data reflects a universal truth. This book will lead the reader through the groves wherein lurk some of the brightest flowers of Number Theory, as it simultaneously encourages the reader to investigate, analyze, conjecture, and ultimately prove their 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 1990's. Math 42 was designed to attract non-science 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 one introduces an audience 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 never 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, a mind that is not afraid to experiment, to make mistakes and profit from them, to accept some frustrations 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.

Table of Contents
Preface.
Contents.
Introduction.
Chapter 1. What is Number Theory?
Chapter 2. Pythagorean Triples
Chapter 3. Pythagorean Triples and the Unit Circle
Chapter 4. Sums of Higher Powers and Fermat's Last Theorem
Chapter 5. Divisibility and the Greatest Common Divisor
Chapter 6. Linear Equations and the Greatest Common Divisor
Chapter 7. Factorization and the Fundamental Theorem of Arithmetic
Chapter 8. Congruences
Chapter 9. Congruences, Powers, and Fermat's Little Theorem
Chapter 10. Congruences, Powers, and Euler's Formula
Chapter 11. Euler's Phi Function
Chapter 12. Prime Numbers
Chapter 13. Counting Primes
Chapter 14. Mersenne Primes
Chapter 15. Mersenne Primes and Perfect Numbers
Chapter 16. Powers Modulo m and Successive Squaring
Chapter 17. Computing k'th Roots Modulo m
Chapter 18. Powers, Roots, and "Unbreakable" Codes
Chapter 19. Euler's Phi Function and Sums of Divisors
Chapter 20. Powers Modulo p and Primitive Roots
Chapter 21. Primitive Roots and Indices
Chapter 22. Squares Modulo p
Chapter 23. Is -1 a Square Modulo p? Is 2?
Chapter 24. Quadratic Reciprocity
Chapter 25. Which Primes Are Sums of Two Squares?
Chapter 26. Which Numbers Are Sums of Two Squares?
Chapter 27. The Equation X^4+Y^4=Z^4
Chapter 28. Square-Triangular Numbers Revisited
Chapter 29. Pell's Equation
Chapter 30. Diophantine Approximation
Chapter 31. Diophantine Approximation and Pell's Equation
Chapter 32. Cubic Curves and Elliptic Curves
Chapter 33. Elliptic Curves With Few Rational Points
Chapter 34. Points on Elliptic Curves Modulo p
Chapter 35. Defect Bounds and Modularity Patterns
Chapter 36. Elliptic Curves and Fermat's Last Theorem
Further Reading
Appendix A. Factorization of Small Composite Integers
Appendix B. A List of Primes
Index

Introduction
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" which 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, which command attention. Far more intriguing are the relationships which 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 20th 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
32+42=52,
but there are many others, such as
52+122=132, 202+212=292, and 282+452=532.
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 which 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 32478543743921429837645 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 which 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 which are so secure that even the National Security Agency is unable to break them. So much for G.H. Hardy's singularly unprophetic remark in 1940 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. There are Fermat equations and Pell equations, Pythagorean triples and elliptic curves, unbreakable codes and much much more. You will meet all of these, and many others, as we journey through the Theory of Numbers.


Guide for the Reader

 Number theory is both fun and exciting. It's fun to experiment with numbers and exciting to discover beautiful patterns and relationships. The goal of this book is to help you experience both the pleasure of experimentation and the thrill of discovery. Along the way, of course, you'll learn many number theoretic facts and techniques, and I hope you will enjoy these in the same way you might enjoy a favorite novel or play or symphony. But the real thrill will come when you make a discovery of your own, so don't be afraid to experiment and don't be afraid to fail at first. Most experiments in any science are failures. It is only by persevering through each setback that one eventually achieves success, and the satisfaction of success is made all the more sweet by the intense effort leading up to it.

The tone of this book is light and informal, which is not to say that all of the material is easy. However, anyone with a solid grounding in high school algebra and an eager and questioning mind will do fine. (The latter requirement is far more important than the former.) Scattered throughout the book are exercises of varying degrees of difficulty, ranging from simple calculations illustrating the material to open-ended questions designed to stretch your intellect. Rather than including long lists of problems, I have tried to include just the right number so that you will be able to work on all of them. For extra practice, there are some additional problems included in a section at the end of the book. Keep in mind that the real goals are discovery and understanding. Some problems have no right or wrong answer. A good question invites you to say as much as possible about a certain phenomenon. That's how mathematicians (and scientists) carry out their investigations.


Guide for the Instructor

 This book is designed to be used as a text for a one semester course in undergraduate number theory or for an independent study or reading course. It contains approximately one and a half semesters worth of material, which gives the instructor some flexibility in the choice of topics. The first 11 chapters are basic, and probably most instructors will want to continue through RSA encoding in Chapter 18, since in my experience, this is one of the students' favorite topics. There are now two ways to proceed. One possibility is to cover primitive roots, quadratic reciprocity, sums of squares, and Pell's equation. With this approach, I have found that it is possible to cover Chapter 1-29 comfortably in one semester. The second possibility is to skip directly from Chapter 18 to Chapter 27. This leaves time to cover Fermat's equation for exponent 4, Pell's equation, Diophantine approximation, and elliptic curves in Chapters 27-36. In either case, a good final project is to have the students read a few of the omitted chapters and do the exercises. They should also be encouraged (if not required) to look at the additional exercises included at the end of the book.

Most of the non-numerical 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 repeatedly stressed. You can make them 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 will always raise 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.

Number theory is not easy, so there's no point in trying to convince the students that it is. Instead, this book shows the reader that he or she is capable of mastering a difficult subject and experiencing the intense satisfaction of intellectual discovery. The instructor's reward 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, or Derive, and with rare exceptions all exercises 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 me to make a 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), RSA encoding and decoding (Chapters 16-18), quadratic reciprocity (Chapter 24), writing numbers as sums of two squares (Chapters 25-26), and adding rational points on elliptic curves (Chapter 32). 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. The moral is that computers are useful as a tool for experimentation, and that one can learn by teaching a computer how to perform number theoretic calculations, but prepackaged programs merely provide a crutch which will prevent you from learning to walk on your own.


Send questions and comments to jhs@gauss.math.brown.edu
Go back to the Home Page of Friendly Introduction ...