Number Theory: A Lively Introduction with Proofs, Applications, and Stories

Front Cover
ISBN 13: 978-0470-42413-1
Title Page
Contents
Preface
Structure of the Text
To the Student
To the Instructor
Acknowledgments
Prologue. Number Theory Through the Ages or An Anachronistic Assembly
Chapter 1 (Pythagoras, 569-ca. 500 BCE)
Chapter 1. Numbers, Rational and Irrational or The Greek System
1.1 Numbers and the Greeks
A pair of protracted Panhellenic pathways
EXERCISES 1.1
1.2 Numbers You Know
Fun Facts
EXERCISES 1.2
1.3 A First Look at Proofs
Direct proof
Indirect proof
The converse
The contrapositive
Understanding why the contrapositive is equivalent
The axiomatic approach
EXERCISES 1.3
1.4 Irrationality of √2
Proof that √2 is irrational
Fun Facts
lncommensurability
Fun Facts
EXERCISES 1.4
1.5 Using Quantifiers
The existential and universal quantifiers
Proving statements with quantifiers
The order of quantifiers in a statement
Negating a statement containing a quantifier
EXERCISES 1.5
Chapter 2 (Emmy Noether, 1882-1935)
Chapter 2. Mathematical Induction
2.1 The Principle of Mathematical Induction
EXERCISES 2.1
2.2 Strong Induction and the Well-Ordering Principle
Naomi's Numerical Proof Preview: Example 1
2.2.1 THE PRINCIPLE OF STRONG INDUCTION
Why strong induction is valid: An intuitive explanation
The Well-Ordering Principle
2.2.2 THE WELL-ORDERING PRINCIPLE
EXERCISES 2.2
2.3 The Fibonacci Sequence and the Golden Ratio
The Fibonacci numbers
The golden ratio
Fibonacci numbers and plant phyllotaxis
EXERCISES 2.3
2.4 The Legend of the Golden Ratio
Mathematical properties of the golden ratio
Misconceptions about φ's appearance in art, architecture, and nature
Plant phyllotaxis: One place φ, really does crop up in nature
Further Reading
EXERCISES 2.4
Chapter 3 (Eratosthenes, 216-194 BCE)
Chapter 3. Divisibility and Primes
3.1 Basic Properties of Divisibility
Linear combinations
EXERCISES 3.1
3.2 Prime and Composite Numbers
A burning question
The existence of prime factorizations
EXERCISES 3.2
3.3 Patterns in the Primes
There are infinitely many primes
Is it prime?
The sieve of Eratosthenes
The Prime Number Theorem
A formula for primes?
EXERCISES 3.3
3.4 Common Divisors and Common Multiples
EXERCISES 3.4
3.5 The Division Theorem
A class divided
A geometric view of the Division Theorem
Proof of the Division Theorem
EXERCISES 3.5
3.6 Applications of gcd and lcm
Gears
Pitch perception and the missing fundamental
EXERCISES 3.6
Chapter 4 (Euclid, roughly 347-287 BCE)
Chapter 4. The Euclidean Algorithm or Tales of a Master Baker
4.1 The Euclidean Algorithm
Euclid's story
EXERCISES 4.1
4.2 Finding the Greatest Common Divisor
A new way to find the gcd
Euclid's insight
Euclidean Algorithm yields the gcd
The Euclidean Algorithm is fast
The Euclidean Algorithm and the Fibonacci numbers
The Euclidean Algorithm is good as gold!
A computational note
EXERCISES 4.2
4.3 A Greeker Argument that √2 Is Irrational
The Euclidean Algorithm with fractions
The Euclidean Algorithm with irrational numbers
EXERCISES 4.3
Chapter 5 (Diophantus, fl. 25 CE)
Chapter 5. Linear Diophantine Equations or General Potato Theory
5.1 The Equation aX+bY=1
Diophantus and the potato
Linear Diophantine equations
Graphing Solutions to a Linear Diophantine Equation
EXERCISES 5.1
5.2 Using the Euclidean Algorithm to Find a Solution
Heavier bricks
Sonny's solution
Solving aX + bY = 1
EUCLID'S ROYAL ROAD TO SOLVING LINEAR DIOPHANTINE EQUATIONS
EXERCISES 5.2
5.3 The Diophantine Equation aX+bY=n
A pile of potatoes
GCD AS A LINEAR COMBINATION
EXERCISES 5.3
5.4 Finding All Solutions to a Linear Diophantine
Striking a new balance
EUCLID'S LEMMA
EXERCISES 5.4
Chapter 6 (Marin Mersenne, 1588-1648)
Chapter 6. The Fundamental Theorem of Arithmetic or Monopolizing the Internet
6.1 The Fundamental Theorem
Mersenne in his prime
Naomi's Numerical Proof Preview: Fundamental Theorem of Arithmetic (6.1.1)
A basic property of primes
Enioying the view
EXERCISES 6.1
6.2 Consequences of the Fundamental Theorem
Finding all the divisors of a number
Prime factorizations and the gcd
Prime factorizations and the lcm
Periodical cicadas and the lcm
EXERCISES 6.2
Chapter 7 (Carl Friedrich Gauss,
1777-1855)
Chapter 7. Modular Arithmeticor Interplanetary Math
7.1 Congruence Modulo n
Gauss's mathematical iourney
Reducing a number modulo n
Congruence classes
One more useful fact about mods
EXERCISES 7.1
7.2 Arithmetic with Congruences
Divisibility tests
EXERCISES 7.2
7.3 Check-Digit Schemes
U.S. Postal money orders
Universal Product Codes
International Standard Book Numbers
Fun Facts
EXERCISES 7.3
7.4 The Chinese Remainder Theorem
Food for thought
Fun Facts
The Chinese Remainder Theorem and congruences in composite moduli
EXERCISES 7.4
7.5 The Gregorian Calendar
Fun Facts
Finding the Doomsday for any year
Finding the day of the week for any date
TABLE 7.5.2 Dates that always occur on the same day of the week as the Doomsday
Using the Doomsday method for other centuries
EXERCISES 7.5
7.6 The Mayan Calendar
Fun Facts
The calendar round
The Tzolkin
Finding the date in the era
EXERCISES 7.6
Chapter 8 (Alan Turing, 1912-1954)
Chapter 8. Modular Number Systems
8.1 The Number System Zn: An Informal View
A new number system
Arithmetic properties of Z6
Patterns in the tables
EXERCISES 8.1
8.2 The Number System Zn: Definition and Basic Properties
Elements of Zn are congruence classes
Arithmetic with congruence classes
Definition of Zn
The operations on Zn are well defined
Zn is a ring
EXERCISES 8.2
8.3 Multiplicative Inverses in Zn
A closer look at the multiplication tables
Multiplicative inverses
Finding multiplicative inverses without a table
Cancellation property
Zp is a field
When does xy = 0?
Good rows
Finding a number in a row
Wilson's Theorem
EXERCISES 8.3
8.4 Elementary Cryptography
Turing's travels
Overview of cryptography
Encryption using modular addition
Fun Facts
EXERCISES 8.4
8.5 Encryption Using Modular Multiplication
Encrypting and decrypting with modular multiplication tables
Truffle trouble
Decrypting without using the table
EXERCISES 8.5
Chapter 9 (Pierre de Fermat, 1601-1665)
Chapter 9. Exponents Modulo n
9.1 Fermat's Little Theorem
The Grapes of Math
Exponents in Zn
A pattern perceptible
Proof of Fermat's Little Theorem
EXERCISES 9.1
9.2 Reduced Residues and the Euler φ-Function
Reduced residues
Reduced residue multiplication tables
The Euler φ-Function
EXERCISES 9.2
9.3 Euler's Theorem
Proof of Euler's Theorem
Repeated squaring: an efficient method for modular exponentiation
Repeated squaring is lightning fast
EXERCISES 9.3
9.4 Exponentiation Ciphers with a Prime Modulus
Encryption by exponentiation modulo 29
Decryption using Fermat's Little Theorem
Verifying that decryption undoes encryption
Examples of encryption and decryption
EXERCISES 9.4
9.5 The RSA Encription Algorithm
Public key cryptography
The RSA algorithm
Factoring Huge Numbers
Verifying that decryption undoes encryption
Examples of encryption and decryption with RSA
The security of RSA depends on the difficulty of factoring
Wanted: large prime numbers
The history of public key cryptography and RSA
Quantum factoring
EXERCISES 9.5
Chapter 10 (Joseph Louis Lagrange, 1736-1813)
Chapter 10. Primitive Roots
10.1 The Order of an Element of Z_n
Lagrange's day in court
The order of an integer modulo n
Perfect shuffles
EXERCISES 10.1
10.2 Solving Polynomial Equations in Z_n
Your high school days
Fun Facts
Polynomials over Zn
How many roots can a polynomial have?
Solutions to x^m = 1
EXERCISES 10.2
10.3 Primitive Roots
Definition of primitive root
Existence of primitive roots in a prime modulus
EXERCISES 10.3
10.4 Applications of Primitive Roots
Discrete logarithms
Diffie-Hellman key exchange
Finding a primitive root modulo a large prime
Random and pseudorandom numbers
Fun Facts
The period of a repeating decimal
EXERCISES 10.4
Chapter 11. Quadratic Residues
11.1 Squares Modulo n
EXERCISES 11.1
Which numbers are squares modulo n?
Square roots in Zn
How many quadratic residues are there?
The Legendre symbol
EXERCISES 11.1
11.2 Euler's Identity and the Quadratic Character of -1
Another way to find the Legendre symbol
Euler's Identity
When is - 1 a square modulo p?
The Legendre symbol is multiplicative
EXERCISES 11.2
11.3 The Law of Quadratic Reciprocity
Statement of the Law of Quadratic Reciprocity
Restatement of the Law
EXERCISES 11.3
11.4 Gauss's Lemma
The lazy multiplication table
Gauss's Lemma
When is 2 a square mod p?
EXERCISES 11.4
11.5 Quadratic Residues and Lattice Points
Keeping careful count of quotients
Eisenstein's Lemma
Proof of Eisenstein's Lemma
Visualizing Eisenstein's Lemma
EXERCISES 11.5
11.6 Proof of Quadratic Reciprocity
A picture-perfect proof
Proof of the Law
The long arm of the Law
EXERCISES 11.6
Chapter 12 (Paul Erdős, 1913-1996)
Chapter 12. Primality Testing
12.1 Primality Testing
Probabilistic primality testing
Witnesses to compositeness
Factoring Is Much Harder than Determining Compositeness
Fermat fooled
Fun Facts
Characterizing Carmichael
EXERCISES 12.1
12.2 Continued Consideration of Carmichael Numbers
Numbers with a square factor have many Fermat witnesses
Carmichael numbers are divisible by at least three primes
EXERCISES 12.2
12.3 The Miller-Rabin Primality Test
An improvement on Fermat
The Miller-Rabin Miracle
Miller-Rabin meets the Prime Number Theorem
Miller-Rabin goes deterministic?
Fun Facts
EXERCISES 12.3
Fun Fact
12.4 Two Special Polynomial Equations in Z_p
Solutions to x^m = 1
Solutions to X^m = -1
EXERCISES 12.4
12.5 Proof that Miller-Rabin Is Effective
Working one prime at a time
Proof of the effectiveness of the Miller-Rabin Test
EXERCISES 12.5
12.6 Prime Certificates
The two powers
Short proofs of compositeness
Short proofs of primality
P versus NP
Fun Facts
EXERCISES 12.6
12.7 The AKS Deterministic Primality Test
The return of the king
The AKS algorithm
Fun Facts
A clever shortcut
EXERCISES 12.7
Chapter 13 (Leonhard Euler, 1707-1783)
Chapter 13. Gaussian Integers
13.1 Definition of the Gaussian Integers
The Gaussian integers form a ring
A geometric view of the Gaussian integers
The norm of a Gaussian integer
Visualizing sums and products of Gaussian integers
EXERCISES 13.1
13.2 Divisibility and Primes in Z[i]
Divisibility in Z[i]
Primes in Z[i]
The set of all multiples of a Gaussian integer
EXERCISES 13.2
13.3 The Division Theorem for the Gaussian Integers
Field of greens
The Division Theorem
EXERCISES 13.3
13.4 Unique Factorization in Z[i]
Linear Diophantine equations in the Gaussian integers
The Fundamental Theorem of Gaussian Arithmetic
EXERCISES 13.4
13.5 Gaussian Primes
Factoring integers into products of Gaussian integers
EXERCISES 13.5
13.6 Fermat's Two Squares Theorem
A pattern in the primes
Fun Facts
EXERCISES 13.6
Chapter 14 (Srinivasa Ramanuian, 1887-1920)
Chapter 14. Continued Fractions or A Cantankerous Collaboration
14.1 Expressing Rational Numbers as Continued Fractions
The good doctor
Introducing continued fractions
Continued fractions and the Euclidean Algorithm
EXERCISES 14.1
14.2 Expressing Irrational Numbers as Continued Fractions
Finding continued fraction expansions of irrational numbers
Periodic continued fractions
Classification of simple continued fractions
EXERCISES 14.2
14.3 Approximating Irrational Numbers Using Continued Fractions
Decimal approximation of √2
Continued fraction approximation of irrational numbers
Early History of 355/113 as an approximation to π
The circle of fifths
EXERCISES 14.3
14.4 Proving That Convergents are Fantastic Approximations
Finding the numerators and denominators of convergents
A useful pattern in the tables of numerators and denominators
Convergents as rational approximations of irrational numbers
Convergents give the best approximations
EXERCISES 14.4
Chapter 15 (Sophie Germain, 1776-1831)
Chapter 15. Some Nonlinear Diophantine Equations
15.1 Pell's Equation
Going straight to Pell
Fun Facts
One solution, many solutions
The number system Z[√d]
Proof of existence of solutions to Pell's equation
EXERCISES 15.1
15.2 Fermat's Last Theorem
Widening the margin
THEOREM 15.2.1 FERMAT' S LAST THEOREM
A useful lemma
A Lamé idea
EXERCISES 15.2
15.3 Proof of Fermat's Last Theorem for n=4
Pythagorean Triples
Fun Facts
THEOREM 15.3.1 PYTHAGOREAN TRIPLE THEOREM
Euler's proof of Fermat's Last Theorem for n = 4
EXERCISES 15.3
15.4 Germain's Contributions to Fermat's Last Theorem
Beyond Germain primes
THEOREM 15.4.5 GERMAIN'S THEOREM
EXERCISES 15.4
15.5 A Geometric Look at the Equation x⁴+y⁴=z²
Fun Facts
THEOREM 15.5.1 FERMAT'S RIGHT TRIANGLE THEOREM
A method for solving any Diophantine equation?
EXERCISES 15.5
Index
ABC
D
EF
GH
IJKL
MN
OP
Q
RS
TUVWYZ