number theory

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