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