Front Matter
TEXTBOOKS in MATHEMATICS
Dedication
Preface
Introduction
1 Diophantine Equations
2 Modular Arithmetic
3 The Distribution of Primes
4 Cryptography
Chapter 1 Divisibility
1.1 What Is a Proof?
Definition 1.1.
1.1.1 Proof by Contradiction
1.2 Divisibility
Definition 1.2.
Examples.
Remark.
Proposition 1.3.
Example.
Proposition 1.4.
Corollary 1.5.
Examples.
CHECK YOUR UNDERSTANDING2
1.3 Euclid's Theorem
Definition 1.6.
Lemma 1.7.
Example.
Euclid's Theorem.
Another proof of Euclid's Theorem.
CHECK YOUR UNDERSTANDING
1.4 Euclid's Original Proof
1.5 The Sieve of Eratosthenes
Proposition 1.8.
CHECK YOUR UNDERSTANDING
1.6 The Division Algorithm
The Division Algorithm.
Examples.
CHECK YOUR UNDERSTANDING
1.6.1 A Cryptographic Application
1.7 The Greatest Common Divisor
Definition 1.9.
Examples.
Definition 1.10.
Examples.
Remark.
Proposition 1.11.
CHECK YOUR UNDERSTANDING
1.8 The Euclidean Algorithm
Euclidean Algorithm.
FIGURE 1.1 Computation of gcd(48, 21).
1.8.1 The Extended Euclidean Algorithm
Theorem 1.12.
Theorem 1.13.
Proposition 1.14.
CHECK YOUR UNDERSTANDING
1.9 Other Bases
Example.
Example.
Example.
CHECK YOUR UNDERSTANDING
1.10 Fermat and Mersenne Numbers
Proposition 1.15.
Proposition 1.16.
1.11 Chapter Highlights
1.12 Problems
1.12.1 Exercises
Section 1.2: Divisibility
Section 1.3: Euclid's Theorem
Section 1.6: The Division Algorithm
Section 1.7: The Greatest Common Divisor
Section 1.8: The Euclidean Algorithm
Section 1.9: Other Bases
Section 1.10: Fermat and Mersenne Numbers
1.12.2 Computer Explorations
1.12.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 2 Linear Diophantine Equations
2.1 ax + by = c
Theorem 2.1.
Corollary 2.2.
CHECK YOUR UNDERSTANDING
2.2 The Postage Stamp Problem
The Postage Stamp Problem:
Proposition 2.3.
Proposition 2.4.
2.3 Chapter Highlights
2.4 Problems
2.4.1 Exercises
Section 2.1: ax + by = c
Section 2.2: The Postage Stamp Problem
2.4.2 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 3 Unique Factorization
3.1 Preliminary Results
Corollary 3.1.
Theorem 3.2.
Remark.
Corollary 3.3.
Proposition 3.4.
CHECK YOUR UNDERSTANDING
3.2 The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic.
Lemma 3.5.
Proposition 3.6.
Proposition 3.7.
Example.
Definition 3.8.
Examples.
Proposition 3.9.
Example.
CHECK YOUR UNDERSTANDING
3.3 Euclid and the Fundamental Theorem of Arithmetic
Book VII, Proposition 30:
Book VII, Proposition 31:
Book IX, Proposition 14:
3.4 Chapter Highlights
3.5 Problems
3.5.1 Exercises
3.5.2 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 4 Applications of Unique Factorization
4.1 A Puzzle
Proposition 4.1.
Examples.
CHECK YOUR UNDERSTANDING
4.2 Irrationality Proofs
Theorem 4.2.
Theorem 4.3.
Examples.
CHECK YOUR UNDERSTANDING
4.3 The Rational Root Theorem
Theorem 4.4. (Rational Root Theorem)
Examples.
CHECK YOUR UNDERSTANDING
4.4 Pythagorean Triples
Questions:
Theorem 4.5.
Examples.
Lemma 4.6.
Lemma 4.7.
Remark.
CHECK YOUR UNDERSTANDING
4.5 Differences of Squares
Theorem 4.8.
Examples.
CHECK YOUR UNDERSTANDING
4.6 Chapter Highlights
4.7 Problems
4.7.1 Exercises
Section 4.1: A Puzzle
Section 4.2: Irrationality Proofs
Section 4.3: The Rational Root Theorem
Section 4.4: Pythagorean Triples
Section 4.5: Differences of Squares
4.7.2 Computer Explorations
Remark:
4.7.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 5 Congruences
5.1 Definitions and Examples
Definition 5.1.
Examples.
Proposition 5.2.
Proposition 5.3.
Examples.
Remark.
Proposition 5.4.
Proposition 5.5.
Corollary 5.6.
Proposition 5.7.
Proposition 5.8.
Remark.
Proposition 5.9.
Corollary 5.10.
Remark.
CHECK YOUR UNDERSTANDING
5.2 Modular Exponentiation
CHECK YOUR UNDERSTANDING
5.3 Divisibility Tests
Proposition 5.11.
Examples.
Proposition 5.12.
Examples.
Proposition 5.13.
Corollary 5.14.
Example.
Remark.
Proposition 5.15.
Corollary 5.16.
Examples.
CHECK YOUR UNDERSTANDING
5.4 Linear Congruences
Theorem 5.17.
Corollary 5.18.
Examples.
Example.
Definition 5.19.
Examples.
Corollary 5.20.
Example.
Example.
Example.
Example.
CHECK YOUR UNDERSTANDING
5.5 The Chinese Remainder Theorem
Theorem 5.21. (Chinese Remainder Theorem)
Algorithm for Solving the Chinese Remainder Theorem.
Example.
Proposition 5.22.
CHECK YOUR UNDERSTANDING
5.6 Fractions Mod m
Example.
5.7 Queens on a Chessboard
5.8 Chapter Highlights
5.9 Problems
5.9.1 Exercises
Section 5.1: Definitions and Examples
Section 5.2: Modular Exponentiation
Section 5.3: Divisibility Tests
Section 5.4: Linear Congruences
Section 5.5: The Chinese Remainder Theorem
5.9.2 Computer Explorations
5.9.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 6 Fermat, Euler, Wilson
6.1 Fermat's Theorem
Theorem 6.1.
Remark.
Example.
Example.
Example.
Corollary 6.2.
Warning.
Proof 1.
Lemma 6.3.
Proof 2.
Lemma 6.4.
Example.
CHECK YOUR UNDERSTANDING
6.2 Euler's Theorem
Definition 6.5.
Example.
Proposition 6.6.
Proposition 6.7.
Theorem 6.8.
Example.
Theorem 6.9.
Remark.
Lemma 6.10.
Example.
Example.
Corollary 6.11.
Example.
Example.
CHECK YOUR UNDERSTANDING
6.3 Wilson's Theorem
Theorem 6.12.
Example.
Example.
Corollary 6.13.
Example.
6.4 Chapter Highlights
6.5 Problems
6.5.1 Exercises
Section 6.1: Fermat's Theorem
Section 6.2: Euler's Theorem
Section 6.3: Wilson's Theorem
6.5.2 Computer Explorations
Remark:
6.5.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 7 Cryptographic Applications
7.1 Introduction
7.2 Shift and Affine Ciphers
Warning:
CHECK YOUR UNDERSTANDING
7.3 Vigenère Ciphers
FIGURE 7.1 Frequencies of letters in English.
FIGURE 7.2 Frequencies of letters in ciphertext.
FIGURE 7.3 Frequencies of letters in positions 1,4, 7, ···.
FIGURE 7.4 Frequencies of letters in positions 2, 5, 8, ···.
FIGURE 7.5 Frequencies of letters in positions 3, 6, 9, ···.
7.4 Transposition Ciphers
CHECK YOUR UNDERSTANDING
7.5 RSA
RSA Setup
RSA Encryption
RSA Decryption
Example.
Remarks:
Proposition 7.1.
Example.
CHECK YOUR UNDERSTANDING
7.6 Stream Ciphers
FIGURE 7.6 Stream cipher encryption: pn = plaintext bit, xn = key bit, cn = ciphertext bit.
One-time pad
Linear Feedback Shift Registers (LFSR)
FIGURE 7.7 LFSR for xn+4 ≡ xn + xn+2 (mod 2).
CHECK YOUR UNDERSTANDING
7.7 Block Ciphers
CHECK YOUR UNDERSTANDING
7.8 Secret Sharing
CHECK YOUR UNDERSTANDING
7.9 Chapter Highlights
7.10 Problems
7.10.1 Exercises
Section 7.2: Shift and Affine Ciphers
Section 7.4: Transposition Ciphers
Section 7.5: RSA
Section 7.6: Stream Ciphers
Section 7.7: Block Ciphers
Section 7.8: Secret Sharing
7.10.2 Computer Explorations
7.10.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 8 Order and Primitive Roots
8.1 Orders of Elements
Example.
Theorem 8.1.
Corollary 8.2.
Example.
CHECK YOUR UNDERSTANDING:
8.1.1 Fermat Numbers
Proposition 8.3.
Remark.
8.1.2 Mersenne Numbers
Proposition 8.4.
8.2 Primitive Roots
Example.
Example.
Proposition 8.5.
Proposition 8.6.
Proposition 8.7.
Example.
Corollary 8.8.
Example.
Theorem 8.9.
Example.
Example.
Proposition 8.10.
CHECK YOUR UNDERSTANDING:
8.3 Decimals
Proposition 8.11.
Example.
Theorem 8.12.
CHECK YOUR UNDERSTANDING:
8.3.1 Midy's Theorem
Theorem 8.13.
8.4 Card Shuffling
8.5 The Discrete Log Problem
Example.
8.6 Existence of Primitive Roots
Proposition 8.14.
Remark.
Lemma 8.15.
CHECK YOUR UNDERSTANDING
8.7 Chapter Highlights
8.8 Problems
8.8.1 Exercises
Section 8.1: Orders of Elements
Section 8.2: Primitive Roots
Section 8.3: Decimals
Section 8.5: The Discrete Log Problem
8.8.2 Computer Explorations
8.8.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 9 More Cryptographic Applications
9.1 Diffie—Hellman Key Exchange
Remark:
Example.
CHECK YOUR UNDERSTANDING:
9.2 Coin Flipping over the Telephone
Remarks.
Example.
9.3 Mental Poker
Example.
9.4 Digital Signatures
CHECK YOUR UNDERSTANDING:
9.5 Chapter Highlights
9.6 Problems
9.6.1 Exercises
Section 9.1: Diffie–Hellman Key Exchange
Section 9.2: Coin Flipping over the Telephone
Section 9.3: Mental Poker
Section 9.4: Digital Signatures
9.6.2 Computer Explorations
9.6.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 10 Quadratic Reciprocity
10.1 Squares and Square Roots Mod Primes
Proposition 10.1.
Definition 10.2.
Examples.
Proposition 10.3.
Theorem 10.4.
Remarks.
Example.
Example.
Example.
Example.
Example.
CHECK YOUR UNDERSTANDING:
10.2 Computing Square Roots Mod p
Proposition 10.5.
Example.
Proposition 10.6.
Example.
CHECK YOUR UNDERSTANDING:
10.3 Quadratic Equations
Proposition 10.7.
Example.
Example.
CHECK YOUR UNDERSTANDING:
10.4 The Jacobi Symbol
Warning:
Theorem 10.8.
Example.
CHECK YOUR UNDERSTANDING:
10.5 Proof of Quadratic Reciprocity
Lemma 10.9.
Lemma 10.10.
Example.
Lemma 10.11.
10.6 Chapter Highlights
10.7 Problems
10.7.1 Exercises
Section 10.1: Squares and Square Roots Mod Primes
Section 10.2: Computing Square Roots Mod p
Section 10.3: Quadratic Equations
Section 10.4: The Jacobi Symbol
Section 10.5: Proof of Quadratic Reciprocity
10.7.2 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 11 Primality and Factorization
11.1 Trial Division and Fermat Factorization
Example.
Example.
CHECK YOUR UNDERSTANDING:
11.2 Primality Testing
11.2.1 Pseudoprimes
Proposition 11.1.
Example.
Definition 11.2.
Definition 11.3.
Example.
Proposition 11.4.
Remark:
Example.
Example.
Definition 11.5.
Example.
Example.
11.2.2 Mersenne Numbers
Proposition 11.6.
Example.
Example.
11.3 Factorization
11.3.1 x2 ≡ y2
Proposition 11.7.
Example.
Example.
CHECK YOUR UNDERSTANDING:
11.3.2 Factoring Pseudoprimes and Factoring Using RSA Exponents
Algorithm 11.8.
Example.
Example.
11.4 Coin Flipping over the Telephone
Example.
11.5 Chapter Highlights
11.6 Problems
11.6.1 Exercises
Section 11.1: Trial Division and Fermat Factorization
Section 11.2: Primality Testing
Section 11.3: Factorization
11.6.2 Computer Explorations
11.6.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 12 Sums of Squares
12.1 Sums of Two Squares
Theorem 12.1.
Lemma 12.2.
Lemma 12.3.
Theorem 12.4.
12.1.1 Algorithm for Writing p ≡ 1 (mod 4) as a Sum of Two Squares
CHECK YOUR UNDERSTANDING:
12.2 Sums of Four Squares
Theorem 12.5.
Lemma 12.6.
Example.
Lemma 12.7.
CHECK YOUR UNDERSTANDING
12.3 Other Sums of Powers
12.4 Chapter Highlights
12.5 Problems
12.5.1 Exercises
Chapter 13 Arithmetic Functions
13.1 Perfect Numbers
Definition 13.1.
Examples.
Definition 13.2.
Examples.
Proposition 13.3.
Proposition 13.4.
Example.
Theorem 13.5.
Remark.
CHECK YOUR UNDERSTANDING:
13.2 Multiplicative Functions
Definition 13.6.
Examples.
Proposition 13.7.
Proposition 13.8.
Lemma 13.9.
Example.
Corollary 13.10.
Corollary 13.11.
Corollary 13.12.
Example.
Corollary 13.13.
Proposition 13.14.
CHECK YOUR UNDERSTANDING:
13.3 Chapter Highlights
13.4 Problems
13.4.1 Exercises
13.4.2 Computer Explorations
13.4.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 14 Continued Fractions
14.1 Rational Approximations
Technical point.
Theorem 14.1.
CHECK YOUR UNDERSTANDING:
14.2 Evaluating Continued Fractions
Proposition 14.2.
CHECK YOUR UNDERSTANDING:
14.3 Pell's Equation
Theorem 14.3.
Example.
CHECK YOUR UNDERSTANDING:
14.4 Chapter Highlights
14.5 Problems
14.5.1 Exercises
14.5.2 Computer Explorations
14.5.3 Answers to “CHECK YOUR UNDERSTANDING”
Chapter 15 Recent Developments
15.1 Goldbach's Conjecture and the Twin Prime Problem
Exercise.
Exercise.
15.2 Fermat's Last Theorem
FIGURE 15.1 An elliptic curve.
15.3 The Riemann Hypothesis
Theorem 15.1.
Back Matter
Appendix A Supplementary Topics
A.1 Geometric Series
Proposition A.1.
Proposition A.2.
Example.
CHECK YOUR UNDERSTANDING
A.2 Mathematical Induction
Remark.
CHECK YOUR UNDERSTANDING
A.3 Pascal's Triangle and the Binomial Theorem
Definition A.3.
Proposition A.4.
CHECK YOUR UNDERSTANDING
A.4 Fibonacci Numbers
Definition A.5. The Fibonacci numbers
Theorem A.6.
Corollary A.7.
A.5 Matrices
Example.
CHECK YOUR UNDERSTANDING:
A.6 Problems
A.6.1 Exercises
Section A.1: Geometric Series
Section A.2: Mathematical Induction
Section A.3: Pascal's Triangle and the Binomial Theorem
Section A.4: Fibonacci Numbers
Section A.5: Matrices
A.6.2 Answers to “CHECK YOUR UNDERSTANDING”
Appendix B Answers and Hints for Odd-Numbered Exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Appendix A
Index

Elementary Number Theory takes an accessible approach to teaching students about the role of number theory in pure mathematics and its important applications to cryptography and other areas. The first chapter of the book explains how to do proofs and includes a brief discussion of lemmas, propositions, theorems, and corollaries. The core of the tex