Elementary Number Theory

Contents

1 Some Preliminary Considerations

1.1 Mathematical Induction

1.2 The Binomial Theorem

1.3 Early Number Theory

2 Divisibility Theory in the Integers

2.1 The Division Algorithm

2.2 The Greatest Common Divisor

2.3 The Euclidean Algorithm

2.4 The Diophantine Equation ax+by=c

3 Primes and Their Distribution

3.1 The Fundamental Theorem of Arithmetic

3.2 The Sieve of Eratosthenes

3.3 The Goldbach Conjecture

4 The Theory of Congruences

4.1 Carl Friedrich Gauss

4.2 Basic Properties of Congruence

4.3 Special Divisibility Tests

4.4 Linear Congruences

5 Fermat's Theorem

5.1 Pierre de Fermat

5.2 Fermat's Factorization Method

5.3 The Little Theorem

5.4 Wilson's Theorem

6 Number-Theoretic Functions

6.1 The Functions Ċ and ċ

6.2 The Mobius Inversion Formula

6.3 The Greatest Integer Function

6.4 An Application to the Calendar

7 Euler's Generalization of Fermat's Theorem

7.1 Leonhard Euler

7.2 Euler's Phi-Function

7.3 Euler's Theorem

7.4 Some Properties of the Phi-Function

7.5 An Application to Cryptography

8 Primitive Roots and Indices

8.1 The Order of an Integer Modulo n

8.2 Primitive Roots for Primes

8.3 Composite Numbers Having Prime Roots

8.4 The Theory of Indices

9 The Quadratic Reciprocity Law

9.1 Euler's Criterion

9.2 The Legendre Symbol and Its Properties

9.3 Quadratic Reciprocity

9.4 Quadratic Congruences with Composite Moduli

10 Perfect Numbers

10.1 The Search for Perfect Numbers

10.2 Mersenne Primes

10.3 Fermat Numbers

11 The Fermat Conjecture

11.1 Pythagorean Triples

11.2 The Famous ¡§Last Theorem¡š

12 Representation of Integers as Sums of Squares

12.1 Joseph Louis Lagrange

12.2 Sums of Two Squares

12.3 Sums of More than Two Squares

13 Fibonacci Numbers

13.1 The Fibonacci Sequence

13.2 Certain Identities Involving Fibonacci Numbers

14 Continued Fractions

14.1 Srinivasa Ramanujan

14.2 Finite Continued Fractions

14.3 Infinite Continued Fractions

14.4 Pell's Equation

15 Some Twentieth-Century Developments

15.1 Hardy, Dickson, and Erdos

15.2 Primality Testing and Factorization

15.3 An Application to Factoring: Remote Coin-Flipping

15.4 The Prime Number Theorem