Elementary Number Theory

Description

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