Elementary Introduction to Number Theory

by Long, Calvin T.

• ISBN13: 9780881338362
• ISBN10: 0881338362
• Edition: 3rd
• Format: Hardcover
• Copyright: 1995-01-01
• Publisher: Waveland Pr Inc

Table of Contents

Preface	vii
Preliminary Considerations	1	(38)
Summation and Multiplication Notation	2	(6)
Inductive Reasoning and the Fibonacci Sequence	8	(5)
The Postulates of Mathematical Induction and Well-Ordering	13	(1)
Mathetical Induction	14	(7)
The Well-Ordering Principle	21	(2)
Equivalence of the Principles of Induction and Well-Ordering	23	(1)
The Division Algorithm	24	(2)
Positional Notation	26	(7)
Computational Complexity	33	(6)
Divisibility Properties of Integers	39	(31)
Basic Properties	39	(2)
The Greatest Common Divisor	41	(1)
The Euclidean Algorithm	42	(7)
The Least Common Multiple	49	(4)
The Fundamental Theorem of Arithmetic	53	(6)
Pythagorean Triples	59	(3)
The Greatest Integer Function	62	(8)
Prime Numbers	70	(17)
The Sieve of Eratosthenes	70	(2)
The Infinitude of Primes	72	(5)
The Prime Number Theorem	77	(4)
Mersenne, Fermat, and Perfect Numbers	81	(6)
Congruences	87	(25)
Basic Definitions and Properties	88	(8)
Special Divisibility Criteria	96	(2)
Reduced Residue Systems and the Euler &phis;-Function	98	(7)
Pseudoprimes and Tests for Primality	105	(4)
Some Contacts with Abstract Algebra	109	(3)
Conditional Congruences	112	(46)
Linear Congruences	112	(5)
The Chinese Remainder Theorem	117	(7)
Polynomial Congruences of Degree Greater than 1	124	(5)
Theorems of Lagrange and Wilson	129	(4)
Quadratic Congruences	133	(3)
The Quadratic Reciprocity Law of Gauss	136	(12)
Primitive Roots, Indices, and Power Residues	148	(10)
Cryptography	158	(13)
Caesar Ciphers	159	(4)
Exponentiation Ciphers	163	(3)
Public Key Encryption Systems	166	(5)
Sums of Squares	171	(14)
Sums of Two Squares	171	(5)
Sums of More than Two Squares	176	(5)
Waring's Problem	181	(4)
Multiplicative Number-Theoretic Functions	185	(24)
Definitions	185	(2)
Notation	187	(2)
Multiplicative Number-Theoretic Functions	189	(4)
The Mobius Inversion Formula	193	(3)
The Euler &phis;-Function	196	(4)
Other Inversion Formulas	200	(6)
A Further Inversion Formula	206	(3)
Simple Continued Fractions	209	(24)
Finite Simple Continued Fractions	210	(4)
Convergents	214	(7)
Infinite Simple Continued Fractions	221	(4)
Periodic Simple Continued Fractions	225	(5)
Approximation of Irrationals by Rationals	230	(3)
REFERENCES	233	(2)
Number Theory	233	(1)
Number Theory and Computing	234	(1)
Cryptography	234	(1)
Computer Science	234	(1)
TABLES	235	(18)
Table of Prime Numbers Less than 10,000	235	(4)
Factorizations of Positive Integers Less than 1000	239	(5)
Table of Indices for Primes p, 3 ≤ p ≤ 199	244	(9)
Answers to Selected Problems	253	(37)
Index	290