Number Theory

- Foreword
- 1 Introduction
- 2 Divisibility
- 2.1 Basic properties
- 2.1.1 Divisibility and congruences
- 2.1.2 Divisibility and order relation
- 2.2 Induction and binomial coefficients
- 2.2.1 Proving divisibility by induction
- 2.2.2 Arithmetic of binomial coefficients
- 2.2.3 Derivatives and finite differences
- 2.2.4 The binomial formula
- 2.3 Euclidean division
- 2.3.1 The Euclidean division
- 2.3.2 Combinatorial arguments and complete residue systems
- 2.4 Problems for practice
- 3 GCD and LCM
- 3.1 Bézout's theorem and Gauss' lemma
- 3.1.1 Bézout's theorem and the Euclidean algorithm
- 3.1.2 Relatively prime numbers
- 3.1.3 Inverse modulo n and Gauss' lemma
- 3.2 Applications to diophantine equations and approximations
- 3.2.1 Linear diophantine equations
- 3.2.2 Pythagorean triples
- 3.2.3 The rational root theorem
- 3.2.4 Farey fractions and Pell's equation
- 3.3 Least common multiple
- 3.4 Problems for practice
- 4 The fundamental theorem of arithmetic
- 4.1 Composite numbers
- 4.2 The fundamental theorem of arithmetic
- 4.2.1 The theorem and its first consequences
- 4.2.2 The smallest and largest prime divisor
- 4.2.3 Combinatorial number theory
- 4.3 Infinitude of primes
- 4.3.1 Looking for primes in classical sequences
- 4.3.2 Euclid's argument
- 4.3.3 Euler's and Bonse's inequalities
- 4.4 Arithmetic functions
- 4.4.1 Classical arithmetic functions
- 4.4.2 Multiplicative functions
- 4.4.3 Euler's phi function
- 4.4.4 The Möbius function and its applications
- 4.4.5 Application to squarefree numbers
- 4.5 Problems for practice
- 5 Congruences involving prime numbers
- 5.1 Fermat's little theorem
- 5.1.1 Fermat's little theorem and (pseudo-)primality
- 5.1.2 Some concrete examples
- 5.1.3 Application to primes of the form 4k + 3 and 3k + 2
- 5.2 Wilson's theorem
- 5.2.1 Wilson's theorem as criterion of primality
- 5.2.2 Application to sums of two squares
- 5.3 Lagrange's theorem and applications
- 5.3.1 The number of solutions of polynomial congruences
- 5.3.2 The congruence xd _ 1 (mod p)
- 5.3.3 The Chevalley-Warning theorem
- 5.4 Quadratic residues and quadratic reciprocity
- 5.4.1 Quadratic residues and Legendre's symbol
- 5.4.2 Points on spheres mod p and Gauss sums
- 5.4.3 The quadratic reciprocity law
- 5.5 Congruences involving rational numbers and binomial coefficients
- 5.5.1 Binomial coefficients modulo primes: Lucas' theorem
- 5.5.2 Congruences involving rational numbers
- 5.5.3 Higher congruences: Fleck, Morley, Wolstenholme
- 5.5.4 Hensel's lemma
- 5.6 Problems for practice
- 6 p-adic valuations and the distribution of primes
- 6.1 The yoga of p-adic valuations
- 6.1.1 The local-global principle
- 6.1.2 The strong triangle inequality
- 6.1.3 Lifting the exponent lemma
- 6.2 Legendre's formula
- 6.2.1 The p-adic valuation of n!: the exact formula
- 6.2.2 The p-adic valuation of n!: inequalities
- 6.2.3 Kummer's theorem
- 6.3 Estimates for binomial coefficients and the distribution of prime numbers 6.3.1 Central binomial coefficients and Erdös' inequality
- 6.3.2 Estimating _(n)
- 6.3.3 Bertrand's postulate
- 6.4 Problems for practice
- 7 Congruences for composite moduli
- 7.1 The Chinese remainder theorem
- 7.1.1 Proof of the theorem and first examples
- 7.1.2 The local-global principle
- 7.1.3 Covering systems of congruences
- 7.2 Euler's theorem
- 7.2.1 Reduced residue systems and Euler's theorem
- 7.2.2 Practicing Euler's theorem
- 7.3 Order modulo n
- 7.3.1 Elementary properties and examples
- 7.3.2 Practicing the notion of order modulo n
- 7.3.3 Primitive roots modulo n
- 7.4 Problems for practice
- 8 Solutions to practice problems
- 8.1 Divisibility
- 8.2 GCD and LCM
- 8.3 The fundamental theorem of arithmetic
- 8.4 Congruences involving prime numbers
- 8.5 p-adic valuations and the distribution of primes
- 8.6 Congruences for composite moduli
- Bibliography