Elementary Number Theory

Cover......Page 1
ABOUT THE AUTHOR......Page 5
PREFACE......Page 7
CHAPTER 1. PRELIMINARIES......Page 11
1.1 MATHEMATICAL INDUCTION......Page 12
1.2 THE BINOMIAL THEOREM......Page 19
2.1 EARLY NUMBER THEORY......Page 24
2.2 THE DIVISION ALGORITHM......Page 28
2.3 THE GREATEST COMMON DIVISOR......Page 30
2.4 THE EUCLIDEAN ALGORITHM......Page 37
2.5 THE DIOPHANTINE EQUATION ax +by = c......Page 43
3.1 THE FUNDAMENTAL THEOREM OF ARITHMETIC......Page 50
3.2 THE SIEVE OF ERATOSTHENES......Page 55
3.3 THE GOLDBACH CONJECTURE......Page 61
4.1 CARL FRIEDRICH GAUSS......Page 72
4.2 BASIC PROPERTIES OF CONGRUENCE......Page 74
4.3 BINA RY A ND DECIMAL REPRESENTATIONS OF INTEGERS......Page 80
4.4 LINEAR CONGRUENCES AND THE CHINESE REMAINDER THEOREM......Page 87
5.1 PIERRE DE FERMAT......Page 96
5.2 FERMAT'S LITTLE THEOREM AND PSEUDOPRIMES......Page 98
5.3 WILSON'S THEOREM......Page 104
5.4 THE F ERMAT-KRAITCHIK FAC T ORIZATION METHOD......Page 108
6.1 THE SUM AND NUMBER OF DIVISORS......Page 114
6.2 THE MOBIUS INVERSION FORMULA......Page 123
6.3 THE GREATEST INTEGER FUNCTION......Page 128
6.4 AN APPLICATION TO THE CALENDAR......Page 133
7.1 LEONHARD EULER......Page 140
7.2 EULER'S PHI-FUNCTION......Page 142
7.3 EULER'S THEOREM......Page 147
7.4 SOME PROPERTIES OF THE PHI-FUNCTION......Page 152
8.1 THE ORDER OF AN INTEGER MODULO n......Page 158
8.2 PRIMITIVE ROOTS FOR PRIMES......Page 163
8.3 COMPOSITE NUMBERS HAVING PRIMITIVE ROOTS......Page 169
8.4 THE THEORY OF INDICES......Page 174
9.1 EULER'S CRITERION......Page 180
9.2 THE LEGENDRE SYMBOL AND ITS PROPERTIES......Page 186
9.3 QUADRATIC RECIPROCITY......Page 196
9.4 QUADRATIC CONGRUENCES WITH COMPOSITE MODULI......Page 203
10.1 FROM CAESAR CIPHER TO PUBLIC KEY CRYPTOGRAPHY......Page 208
10.2 THE KNAPSACK CRYPTOSYSTEM......Page 220
10.3 AN APPLICATION OF PRIMITIVE ROOTS TO CRYPTOGRAPHY......Page 225
11.1 MARIN MERSENNE......Page 230
11.2 PERFECT NUMBERS......Page 232
11.3 MERSENNE PRIMES AND AMICABLE NUMBERS......Page 238
11.4 FERMAT NUMBERS......Page 248
12.1 THE EQUATION x2 + y2 = z2......Page 256
12.2 FERMAT'S LAST THEOREM......Page 263
13.1 JOSEPH LOUIS LAGRANGE......Page 272
13.2 SUMS OF TWO SQUARES......Page 274
13.3 SUMS OF MORE THAN TWO SQUARES......Page 283
14.1 FIBONACCI......Page 294
14.2 THE FIBONACCI SEQUENCE......Page 296
14.3 CERTAIN IDENTITIES INVOLVING FIBON ACCI NUMBERS......Page 303
15.1 SRINIVASA RAMANUJAN......Page 314
15.2 FINITE CONTINUED FRACTIONS......Page 317
15.3 INFINITE CONTINUED FRACTIONS......Page 330
15.4 FAREY FRACTIONS......Page 345
15.5 PELL'S EQUATION......Page 348
16.1 HARDY, DICKSON, AND ERDOS......Page 364
16.2 PRIMALITY TESTING AND FACTORIZATION......Page 369
16.3 AN APPLICATION TO FACTORING: REMOTE COIN FLIPPING......Page 382
16.4 THE PRIME NUMBER THEOREM AND ZETA FUNCTION......Page 386
MISCELLANEOUS PROBLEMS......Page 395
GENERAL REFERENCES......Page 398
SUGGESTED FURTHER READING......Page 401
TABLES......Page 404
ANSWERS TO SELECTED PROBLEMS......Page 421
INDEX......Page 432
INDEX OF SYMBOLS......Page 448