Elementary Number Theory

CHAPTER 1. PRELIMINARIES......Page 1
ABOUT THE AUTHOR......Page 5
1.1 MATHEMATICAL INDUCTION......Page 14
1.2 THE BINOMIAL THEOREM......Page 21
2.1 EARLY NUMBER THEORY......Page 26
2.2 THE DIVISION ALGORITHM......Page 30
2.3 THE GREATEST COMMON DIVISOR......Page 32
2.4 THE EUCLIDEAN ALGORITHM......Page 39
2.5 THE DIOPHANTINE EQUATION ax +by = c......Page 45
3.1 THE FUNDAMENTAL THEOREM OF ARITHMETIC......Page 52
3.2 THE SIEVE OF ERATOSTHENES......Page 57
3.3 THE GOLDBACH CONJECTURE......Page 63
4.1 CARL FRIEDRICH GAUSS......Page 74
4.2 BASIC PROPERTIES OF CONGRUENCE......Page 76
4.3 BINA RY A ND DECIMAL REPRESENTATIONS OF INTEGERS......Page 82
4.4 LINEAR CONGRUENCES AND THE CHINESE REMAINDER THEOREM......Page 89
5.1 PIERRE DE FERMAT......Page 98
5.2 FERMAT'S LITTLE THEOREM AND PSEUDOPRIMES......Page 100
5.3 WILSON'S THEOREM......Page 106
5.4 THE F ERMAT-KRAITCHIK FAC T ORIZATION METHOD......Page 110
6.1 THE SUM AND NUMBER OF DIVISORS......Page 116
6.2 THE MOBIUS INVERSION FORMULA......Page 125
6.3 THE GREATEST INTEGER FUNCTION......Page 130
6.4 AN APPLICATION TO THE CALENDAR......Page 135
7.1 LEONHARD EULER......Page 142
7.2 EULER'S PHI-FUNCTION......Page 144
7.3 EULER'S THEOREM......Page 149
7.4 SOME PROPERTIES OF THE PHI-FUNCTION......Page 154
8.1 THE ORDER OF AN INTEGER MODULO n......Page 160
8.2 PRIMITIVE ROOTS FOR PRIMES......Page 165
8.3 COMPOSITE NUMBERS HAVING PRIMITIVE ROOTS......Page 171
8.4 THE THEORY OF INDICES......Page 176
9.1 EULER'S CRITERION......Page 182
9.2 THE LEGENDRE SYMBOL AND ITS PROPERTIES......Page 188
9.3 QUADRATIC RECIPROCITY......Page 198
9.4 QUADRATIC CONGRUENCES WITH COMPOSITE MODULI......Page 205
10.1 FROM CAESAR CIPHER TO PUBLIC KEY CRYPTOGRAPHY......Page 210
10.2 THE KNAPSACK CRYPTOSYSTEM......Page 222
10.3 AN APPLICATION OF PRIMITIVE ROOTS TO CRYPTOGRAPHY......Page 227
11.1 MARIN MERSENNE......Page 232
11.2 PERFECT NUMBERS......Page 234
11.3 MERSENNE PRIMES AND AMICABLE NUMBERS......Page 240
11.4 FERMAT NUMBERS......Page 250
12.1 THE EQUATION x2 + y2 = z2......Page 258
12.2 FERMAT'S LAST THEOREM......Page 265
13.1 JOSEPH LOUIS LAGRANGE......Page 274
13.2 SUMS OF TWO SQUARES......Page 276
13.3 SUMS OF MORE THAN TWO SQUARES......Page 285
14.1 FIBONACCI......Page 296
14.2 THE FIBONACCI SEQUENCE......Page 298
14.3 CERTAIN IDENTITIES INVOLVING FIBON ACCI NUMBERS......Page 305
15.1 SRINIVASA RAMANUJAN......Page 316
15.2 FINITE CONTINUED FRACTIONS......Page 319
15.3 INFINITE CONTINUED FRACTIONS......Page 332
15.4 FAREY FRACTIONS......Page 347
15.5 PELL'S EQUATION......Page 350
16.1 HARDY, DICKSON, AND ERDOS......Page 366
16.2 PRIMALITY TESTING AND FACTORIZATION......Page 371
16.3 AN APPLICATION TO FACTORING: REMOTE COIN FLIPPING......Page 384
16.4 THE PRIME NUMBER THEOREM AND ZETA FUNCTION......Page 388
MISCELLANEOUS PROBLEMS......Page 397
GENERAL REFERENCES......Page 400
SUGGESTED FURTHER READING......Page 403
TABLES......Page 406
ANSWERS TO SELECTED PROBLEMS......Page 423
INDEX......Page 434
INDEX OF SYMBOLS......Page 450