Introduction to number theory with cryptography

IntroductionDiophantine EquationsModular ArithmeticPrimes and the Distribution of PrimesCryptographyDivisibilityDivisibilityEuclid's Theorem Euclid's Original Proof The Sieve of Eratosthenes The Division Algorithm The Greatest Common Divisor The Euclidean Algorithm Other BasesLinear Diophantine EquationsThe Postage Stamp Problem Fermat and Mersenne Numbers Chapter Highlights Problems Unique FactorizationPreliminary Results The Fundamental Theorem of Arithmetic Euclid and the Fundamental Theorem of ArithmeticChapter Highlights Problems Applications of Unique Factorization A Puzzle Irrationality Proofs The Rational Root Theorem Pythagorean Triples Differences of Squares Prime Factorization of Factorials The Riemann Zeta Function Chapter Highlights Problems CongruencesDefinitions and Examples Modular Exponentiation Divisibility TestsLinear Congruences The Chinese Remainder TheoremFractions mod m Fermat's Theorem Euler's Theorem Wilson's Theorem Queens on a Chessboard Chapter Highlights Problems Cryptographic ApplicationsIntroduction Shift and Affine Ciphers Secret Sharing RSA Chapter Highlights Problems Polynomial Congruences Polynomials Mod Primes Solutions Modulo Prime PowersComposite Moduli Chapter Highlights Problems Order and Primitive RootsOrders of Elements Primitive Roots DecimalsCard Shuffling The Discrete Log Problem Existence of Primitive Roots Chapter Highlights Problems More Cryptographic Applications Diffie-Hellman Key Exchange Coin Flipping over the Telephone Mental Poker The ElGamal Public Key Cryptosystem Digital Signatures Chapter Highlights Problems Quadratic Reciprocity Squares and Square Roots Mod Primes Computing Square Roots Mod p Quadratic Equations The Jacobi Symbol Proof of Quadratic Reciprocity Chapter Highlights Problems Primality and Factorization Trial Division and Fermat Factorization Primality Testing Factorization Coin Flipping over the Telephone Chapter Highlights Problems Geometry of NumbersVolumes and Minkowski's Theorem Sums of Two Squares Sums of Four Squares Pell's Equation Chapter Highlights Problems Arithmetic FunctionsPerfect Numbers Multiplicative Functions Chapter Highlights Problems Continued Fractions Rational Approximations; Pell's Equation Basic TheoryRational Numbers Periodic Continued Fractions Square Roots of Integers Some Irrational Numbers Chapter Highlights Problems Gaussian Integers Complex Arithmetic Gaussian Irreducibles The Division Algorithm Unique Factorization Applications Chapter Highlights Problems Algebraic IntegersQuadratic Fields and Algebraic IntegersUnits Z[√-2] Z[√3] Non-unique Factorization Chapter Highlights Problems Analytic MethodsΣ1/p Diverges Bertrand's Postulate Chebyshev's Approximate Prime Number Theorem Chapter Highlights Problems Epilogue: Fermat's Last Theorem Introduction Elliptic Curves Modularity Supplementary Topics Geometric SeriesMathematical InductionPascal's Triangle and the Binomial TheoremFibonacci NumbersProblems Answers and Hints for Odd-Numbered ExercisesIndex