Topics in Number Theory

Introduction and Acknowledgment

Prerequisites and Notation

Chapter 1. Generalities

1. Divisibility

2. Division Algorithm

3. Primes and Composites

4. Congruence and Their Properties

5. Complete Residue System mod m

6. Chinese Remainder Theorem

Chapter 2. Some Number Theoretic Functions

1. Euler's ‑-Function

2. Greatest Integer Function

3. The Functions (n), ơ (n), and µ (n)

4. Perfect Numbers

5. Mobius Inversion Formula

6. Counting the Number of Monic Irreducible Polynomials over a Finite Field

Chapter 3. Primitive Roots and the Structure of Groups Z_n

1. The Group Z_n

2. Fermat's Little Theorem

3. Euler's Generalization of the Fermat's Little Theorem

4. Mobius -Function Revisited

Chapter 4. Quadratic Residues, Nonresidues, and the Law of Quadratic Reciprocity

1. Legendre Symbol

2. Gauss' Lemma

3. Law of Quadratic Reciprocity

4. Jacobi Symbol

Chapter 5. Representation of Integers as Sums of Squares

1. Sums of Two Squares

2. Sums of Four Squares

Chapter 6. Representing Primes in the Form x2 + Ny2

Chapter 7. Infinitude of Primes

1. Euclid-like Proofs

2. Primes p = 1 (mod n)

3. Euler's Proof of Infinitude of Primes

Chapter 8. Pell's Equation and Continued Fractions

1. Continued Fractions

2. Complete Quotients

3. Reduced Quadratic Irrational

4. Solution of the Pell's Equation x² - Ny² = 1

5. Chakravala “Algorithm” for Finding a Solution of Pell's Equation

Chapter 9. Algebraic Number Theory

1. Euclidean Quadratic Fields

2. Fermat's Last Theorem for Exponent 3

Chapter 10. Computational Number Theory

1. Primality Testing

2. RSA Cryptography

3. Computing an (mod m) by Repeated Squaring

4. Calculating Square Root mod p (p > 2, a Prime)

5. Shank's Baby-Step Giant-Step Discrete Log Algorithm

Chapter 11. Some Bachet Equation

Chapter 12. Some Additional Topics

1. Hensel's Lemma

2. LCM(a, b, c) and GCD(a, b, c)

3. Orders of GL(k,Zn) and SL(k,Zn)

4. Problem of Five Sailors and a Monkey

Appendix 1. First 12 Mersenne Primes

Appendix 2. Algebraic Numbers and Algebraic Integers

Appendix 3. Continued Fraction for square root of n for 2 < n < 500 (non-square n) Appendix 4. “Least solution" of Pell's Equation X2 - NY² = 1

Appendix 5. Test of Divisibility by 7, 11, and 13.

Appendix 6. Calculating Square Roots

Appendix 7. List of primes below 10,000

Appendix 8. Finding Day of the Week - John Conway's Doomsday Algorithm

Appendix 9. Cubic Polynomials with Rational Roots and Critical Points

Problems

Credits and Sources Acknowledged

Glossary

Bibliography

Index