(Ebook) Introduction to Number Theory 2nd Edition by Anthony Vazzana, David Garth, Marty Erickson ISBN 9781498717496 1498717497

Chapter 1 Introduction

1.1 What is number theory?

1.2 The natural numbers

PROPOSITION (Properties of the natural numbers)

Example 1.1

DEFINITION (Order relation)

Example 1.2

PROPOSITION (Trichotomy law)

Exercises

1.3 Mathematical induction

Example 1.3

Example 1.4

Example 1.5

Example 1.6

Exercises

1.4 Notes

The Peano axioms

Chapter 2 Divisibility

2.1 Basic definitions and properties

DEFINITION 2.1

Example 2.2

DEFINITION 2.3

Example 2.4

DEFINITION 2.5

Example 2.6

PROPOSITION 2.7 (Properties of divisibility)

Example 2.8

Exercises

2.2 The division algorithm

THEOREM 2.9 (Division algorithm)

Example 2.10

Exercises

2.3 Representations of integers

PROPOSITION 2.11

DEFINITION 2.12

Example 2.13

Example 2.14

Exercises

Chapter 3 Greatest Common Divisor

3.1 Greatest common divisor

DEFINITION 3.1

Example 3.2

DEFINITION 3.3

Example 3.4

PROPOSITION 3.5

THEOREM 3.6 (GCD as a linear combination)

Example 3.7

COROLLARY 3.8 (Euclid's lemma)

COROLLARY 3.9

DEFINITION 3.10

Example 3.11

PROPOSITION 3.12

Exercises

3.2 The Euclidean algorithm

LEMMA 3.13

Example 3.14

THEOREM 3.15

Exercises

3.3 Linear Diophantine equations

THEOREM 3.16

Example 3.17

Example 3.18

Example 3.19

THEOREM 3.20

THEOREM 3.21

FIGURE 3.1: Solutions to ax + by = c.

Example 3.22

Exercises

3.4 Notes

Euclid

THEOREM (Binet's formula)

PROPOSITION

Exercises

Chapter 4 Primes

4.1 The sieve of Eratosthenes

PROPOSITION 4.1

Example 4.2

ALGORITHM 4.3 (Sieve of Eratosthenes)

Exercises

4.2 The fundamental theorem of arithmetic

LEMMA 4.4

THEOREM 4.5 (Fundamental theorem of arithmetic)

Example 4.6

Exercises

4.3 Distribution of prime numbers

THEOREM 4.7 (Euclid)

PROPOSITION 4.8

CONJECTURE (Twin primes)

CONJECTURE (Goldbach, 1742)

THEOREM (Prime number theorem)

TABLE 4.1: Comparison of π(x) with approximations.

PROPOSITION 4.9

THEOREM (Dirichlet)

THEOREM (Primes in arithmetic progression)

Exercises

4.4 Notes

Eratosthenes

Nonunique factorization and Fermat's Last Theorem

Chapter 5 Congruences

5.1 Residue classes

DEFINITION 5.1

Example 5.2

PROPOSITION 5.3

Example 5.4

PROPOSITION 5.5

DEFINITION 5.6

Example 5.7

DEFINITION 5.8

Example 5.9

Exercises

5.2 Linear congruences

THEOREM 5.10

Example 5.11

COROLLARY 5.12

COROLLARY 5.13

DEFINITION 5.14

Example 5.15

Exercises

5.3 Application: Check digits and the ISBN-10 system

PROPOSITION 5.16

Exercises

5.4 The Chinese remainder theorem

THEOREM 5.17 (Chinese remainder theorem)

Example 5.18

Exercises

Chapter 6 Special Congruences

6.1 Fermat's theorem

Example 6.1

THEOREM 6.2 (Fermat's (little) theorem)

Example 6.3

COROLLARY 6.4

Example 6.5

DEFINITION 6.6

Exercises

6.2 Euler's theorem

DEFINITION 6.7

Example 6.8

Example 6.9

THEOREM 6.10 (Euler's theorem)

Example 6.11

PROPOSITION 6.12

Example 6.13

THEOREM 6.14

Example 6.15

Example 6.16

DEFINITION 6.17

THEOREM

6.3 Wilson's theorem

THEOREM 6.18 (Wilson's theorem)

Example 6.19

THEOREM 6.20

PROPOSITION 6.21

Exercises

6.4 Notes

Leonhard Euler

Chapter 7 Primitive Roots

7.1 Order of an element mod n

DEFINITION 7.1

Example 7.2

Example 7.3

PROPOSITION 7.4

COROLLARY 7.5

PROPOSITION 7.6

Example 7.7

Exercises

7.2 Existence of primitive roots

PROPOSITION 7.8

DEFINITION 7.9

Example 7.10

PROPOSITION 7.11

THEOREM 7.12 (Division algorithm for polynomials)

COROLLARY 7.13

THEOREM 7.14

THEOREM 7.15

Exercises

7.3 Primitive roots modulo composites

THEOREM 7.16

THEOREM 7.17

THEOREM 7.18

Exercises

7.4 Application: Construction of the regular 17-gon

FIGURE 7.1: Argand diagram for the 5th roots of unity.

FIGURE 7.2: Argand diagram for the 17th roots of unity.

Exercises

7.5 Notes

Groups

DEFINITION

Straightedge and compass constructions

Chapter 8 Cryptography

8.1 Monoalphabetic substitution ciphers

Example 8.1

TABLE 8.1: Encryption key

TABLE 8.2: Residue classes for letters

PROPOSITION 8.2

ALGORITHM 8.3 (Affine cipher: encryption)

Example 8.4

ALGORITHM 8.5 (Affine cipher: decryption)

Exercises

8.2 The Pohlig–Hellman cipher

PROPOSITION 8.6

ALGORITHM 8.7 (Pohlig Hellman cipher: encryption)

ALGORITHM 8.8 (Pohlig Hellman cipher: decryption)

Example 8.9

Exercises

8.3 The Massey–Omura exchange

ALGORITHM 8.10 (Massey–Omura exchange)

Example 8.11

Exercises

8.4 The RSA algorithm

PROPOSITION 8.12

ALGORITHM 8.13 (RSA algorithm: encryption)

ALGORITHM 8.14 (RSA algorithm: decryption)

Example 8.15

Exercises

8.5 Notes

Computing powers mod p

RSA cryptography

Chapter 9 Quadratic Residues

9.1 Quadratic congruences

PROPOSITION 9.1

Exercises

9.2 Quadratic residues and nonresidues

DEFINITION 9.2

Example 9.3

PROPOSITION 9.4

THEOREM 9.5 (Euler's criterion)

Example 9.6

DEFINITION 9.7

PROPOSITION 9.8 (Properties of the Legendre symbol)

Example 9.9

Exercises

9.3 Quadratic reciprocity

PROPOSITION 9.10 (Gauss's lemma)

THEOREM 9.11

THEOREM 9.12 (Quadratic reciprocity)

LEMMA 9.13

Example 9.14

PROPOSITION 9.15

Exercises

9.4 The Jacobi symbol

DEFINITION 9.16

Example 9.17

PROPOSITION 9.18 (Properties of the Jacobi symbol)

LEMMA 9.19

THEOREM 9.20 (Quadratic reciprocity for Jacobi symbols)

Example 9.21

Exercises

9.5 Notes

Carl Friedrich Gauss

Chapter 10 Applications of Quadratic Residues

10.1 Application: Construction of tournaments

DEFINITION 10.1

FIGURE 10.1: A graph.

FIGURE 10.2: An oriented graph.

DEFINITION 10.2

DEFINITION 10.3

DEFINITION 10.4

FIGURE 10.3: Rock–paper–scissors tournament.

THEOREM 10.5

FIGURE 10.4: A tournament with property S2.

Exercises

10.2 Consecutive quadratic residues and nonresidues

Example 10.6

PROPOSITION 10.7

COROLLARY 10.8

Exercises

10.3 Application: Hadamard matrices

QUESTION 10.9

THEOREM 10.10 (Hadamard)

DEFINITION 10.11

FIGURE 10.5: Hadamard matrices of orders 2 and 4.

THEOREM 10.12

Example 10.13

CONJECTURE

OPEN PROBLEM

Exercises

Chapter 11 Sums of Squares

11.1 Pythagorean triples

FIGURE 11.1: A familiar right triangle.

DEFINITION 11.1

LEMMA 11.2

THEOREM 11.3

Example 11.4

Exercises

11.2 Gaussian integers

THEOREM 11.5

DEFINITION 11.6

Example 11.7

DEFINITION 11.8

Example 11.9

DEFINITION 11.10

DEFINITION 11.11

PROPOSITION 11.12

COROLLARY 11.13

COROLLARY 11.14

DEFINITION 11.15

Example 11.16

Example 11.17

DEFINITION 11.18

Example 11.19

PROPOSITION 11.20

Example 11.21

THEOREM 11.22

COROLLARY 11.23

Example 11.24

THEOREM 11.25

Exercises

11.3 Factorization of Gaussian integers

THEOREM 11.26 (Division algorithm for Gaussian integers)

Example 11.27

DEFINITION 11.28

Example 11.29

THEOREM 11.30

COROLLARY 11.31

THEOREM 11.32

THEOREM 11.33

THEOREM 11.34

Example 11.35

THEOREM 11.36

Exercises

11.4 Lagrange's four squares theorem

PROPOSITION 11.37

THEOREM 11.38

THEOREM 11.39 (Lagrange)

LEMMA 11.40

THEOREM 11.41

Exercises

11.5 Notes

Diophantus

Chapter 12 Further Topics in Diophantine Equations

12.1 The case n = 4 in Fermat's Last Theorem

THEOREM 12.1

COROLLARY 12.2

COROLLARY 12.3

Exercises

12.2 Pell's equation

Example 12.4

THEOREM 12.5

COROLLARY 12.6

COROLLARY 12.7

Example 12.8

FIGURE 12.1: Solutions to the Pell equation x2 − dy2 = 1.

THEOREM 12.9

THEOREM 12.10

Example 12.11

Exercises

12.3 The abc conjecture

DEFINITION 12.12

CONJECTURE (abc conjecture)

THEOREM (Catalan's conjecture)

CONJECTURE (Fermat–Catalan conjecture)

Exercises

12.4 Notes

Pierre de Fermat

The p-adic numbers

Exercises

Chapter 13 Continued Fractions

13.1 Finite continued fractions

DEFINITION 13.1

Example 13.2

THEOREM 13.3

PROPOSITION 13.4

DEFINITION 13.5

Example 13.6

PROPOSITION 13.7

THEOREM 13.8

COROLLARY 13.9

COROLLARY 13.10

COROLLARY 13.11

Exercises

13.2 Infinite continued fractions

THEOREM 13.12

Example 13.13

THEOREM 13.14

DEFINITION 13.15

THEOREM 13.16

Example 13.17

Exercises

13.3 Rational approximation of real numbers

THEOREM 13.18

COROLLARY 13.19

COROLLARY 13.20

THEOREM 13.21

Example 13.22

THEOREM 13.23

THEOREM 13.24

COROLLARY 13.25

THEOREM 13.26

THEOREM 13.27

THEOREM 13.28 (Hurwitz)

Exercises

13.4 Notes

Continued fraction expansions of e

Continued fraction expansion of tan x

Srinivasa Ramanujan

Exercises

Chapter 14 Continued Fraction Expansions of Quadratic Irrationals

14.1 Periodic continued fractions

DEFINITION 14.1

DEFINITION 14.2

LEMMA 14.3

THEOREM 14.4

Example 14.5

LEMMA 14.6

LEMMA 14.7

DEFINITION 14.8

LEMMA 14.9

THEOREM 14.10

Example 14.11

THEOREM 14.12

Exercises

14.2 Continued fraction factorization

PROPOSITION 14.13

Example 14.14

PROPOSITION 14.15

THEOREM 14.16

Example 14.17

Exercises

14.3 Continued fraction solution of Pell's equation

Example 14.18

FIGURE 14.1: The number is irrational.

Example 14.19

THEOREM 14.20

THEOREM 14.21

LEMMA 14.22

Example 14.23

Exercises

14.4 Notes

Three squares and triangular numbers

FIGURE 14.2: The first four triangular numbers: 1, 3, 6, 10.

THEOREM

Exercises

History of Pell's equation

Exercises

Chapter 15 Arithmetic Functions

15.1 Perfect numbers

DEFINITION 15.1

Example 15.2

PROPOSITION 15.3

PROPOSITION 15.4

Example 15.5

THEOREM 15.6 (Euclid)

PROPOSITION 15.7

THEOREM 15.8 (Euler)

QUESTION

QUESTION

Exercises

15.2 The group of arithmetic functions

DEFINITION 15.9

Example 15.10

Example 15.11

Example 15.12

DEFINITION 15.13

PROPOSITION 15.14

PROPOSITION 15.15

COROLLARY 15.16

PROPOSITION 15.17

Example 15.18

DEFINITION 15.19 (Dirichlet multiplication)

Example 15.20

Example 15.21

THEOREM 15.22

PROPOSITION 15.23

THEOREM 15.24

THEOREM 15.25

Exercises

15.3 Möbius inversion

PROPOSITION 15.26

Example 15.27

THEOREM 15.28 (Möbius inversion formula)

Example 15.29

Example 15.30

PROPOSITION 15.31

Example 15.32

Exercises

15.4 Application: Cyclotomic polynomials

DEFINITION 15.33

Example 15.34

DEFINITION 15.35

Example 15.36

THEOREM 15.37

COROLLARY 15.38

Example 15.39

THEOREM 15.40

COROLLARY 15.41

Example 15.42

Exercises

15.5 Partitions of an integer

DEFINITION 15.43

Example 15.44

TABLE 15.1: Partition numbers p(n, k) for 1 ≤ k ≤ n ≤ 10

TABLE 15.2: Partition numbers p(n) for 1 ≤ n ≤ 100

FIGURE 15.1: The Ferrers diagram of a partition of 12.

FIGURE 15.2: A transpose Ferrers diagram.

THEOREM 15.45

PROPOSITION 15.46

THEOREM 15.47

PROPOSITION 15.48

PROPOSITION 15.49

Example 15.50

PROPOSITION 15.51

FIGURE 15.3: Pentagonal numbers.

DEFINITION 15.52

PROPOSITION 15.53

Example 15.54

THEOREM 15.55 (Euler's pentagonal number theorem)

COROLLARY 15.56

Example 15.57

Exercises

15.6 Notes

The lore of perfect numbers

Pioneers of integer partitions

Chapter 16 Large Primes

16.1 Fermat numbers

DEFINITION 16.1

PROPOSITION 16.2

THEOREM 16.3 (Euler)

THEOREM 16.4 (Lucas)

TABLE 16.1: Fermat numbers and their prime factors

THEOREM 16.5 (Pepin's test)

PROOF (of Theorem 16.5)

Exercises

16.2 Mersenne numbers

DEFINITION 16.6

PROPOSITION 16.7

TABLE 16.2: Exponents p of Mersenne primes 2p − 1 discovered before 2000.

THEOREM (Lucas–Lehmer test)

Exercises

16.3 Prime certificates

THEOREM 16.8 (Lucas)

Example 16.9

THEOREM (Lucas)

Exercises

16.4 Finding large primes

ALGORITHM 16.10 (Finding a large prime using Lucas’ theorem)

Example 16.11

Exercises

Chapter 17 Analytic Number Theory

17.1 Sum of reciprocals of primes

THEOREM 17.1

Exercises

17.2 Orders of growth of functions

DEFINITION 17.2

Example 17.3

Exercises

17.3 Chebyshev's theorem

THEOREM 17.4 (Chebyshev's theorem)

DEFINITION 17.5

Example 17.6

THEOREM 17.7

THEOREM 17.8

LEMMA 17.9

COROLLARY 17.10

LEMMA 17.11 (De Polignac's formula)

THEOREM 17.12

THEOREM 17.13

LEMMA 17.14

Exercises

17.4 Bertrand's postulate

PROPOSITION 17.15

THEOREM 17.16 (Bertrand's postulate)

LEMMA 17.17

Exercises

17.5 The prime number theorem

THEOREM 17.18

THEOREM 17.19

THEOREM 17.20

THEOREM 17.21

Exercises

17.6 The zeta function and the Riemann hypothesis

DEFINITION 17.22

THEOREM 17.23

CONJECTURE (Riemann hypothesis)

Exercises

17.7 Dirichlet's theorem

THEOREM 17.24 (Dirichlet's theorem)

PROPOSITION 17.25

THEOREM 17.26

PROPOSITION 17.27

Exercises

17.8 Notes

Paul Erdős

Chapter 18 Elliptic Curves

18.1 Cubic curves

Example 18.1

FIGURE 18.1: Graph of y2 = x3 − 2x + 4.

Example 18.2

FIGURE 18.2: Graph of y2 = x3 − 4x.

Exercises

18.2 Intersections of lines and curves

FIGURE 18.3: Intersections of lines and a circle.

FIGURE 18.4: Intersection of y2 = x3 + 17 and y = x − 1.

Example 18.3

DEFINITION 18.4

Example 18.5

FIGURE 18.5: Point of intersection multiplicity 2.

THEOREM 18.6

FIGURE 18.6: The line through P and Q intersects the curve at a third point, R.

DEFINITION 18.7

Example 18.8

PROPOSITION 18.9

FIGURE 18.7: Singularities on cubic curves.

DEFINITION 18.10

THEOREM 18.11

COROLLARY 18.12

DEFINITION 18.13

FIGURE 18.8: Tangent line to y2 = x3 + 17 at (− 1, 4).

Example 18.14

THEOREM 18.15

Exercises

18.3 The group law and addition formulas

FIGURE 18.9: Addition of points P and Q.

FIGURE 18.10: Addition of point P with itself.

Example 18.16

DEFINITION 18.17

THEOREM 18.18

THEOREM 18.19

Exercises

18.4 Sums of two cubes

Example 18.20

Exercises

18.5 Elliptic curves mod p

DEFINITION 18.21

Example 18.22

Example 18.23

THEOREM (Hasse)

Example 18.24

Exercises

18.6 Encryption via elliptic curves

Example 18.25

Exercises

18.7 Elliptic curve method of factorization

Example 18.26

DEFINITION 18.27

Example 18.28

THEOREM 18.29

Example 18.30

Exercises

18.8 Fermat's Last Theorem

TABLE 18.1: Values of p, Np, and p + 1 − Np

Exercises

18.9 Notes

Projective space

Associativity of the group law

THEOREM

THEOREM (Bezout's theorem)

THEOREM

Exercises

Back Matter

Appendix A Web Resources

Websites

General Mathematics:

Number Theory (general):

Prime Numbers:

Factoring:

Hilbert's Tenth Problem:

Mathematica:

Maple:

Sage:

Appendix B Notation

References

Index

*Free conversion of into popular formats such as PDF, DOCX, DOC, AZW, EPUB, and MOBI after payment.