1 Divisibility and GCD

Preliminaries

1.1 Divisibility

1.2 The greatest common divisor

1.3 Euclid’s algorithm

2 Prime numbers and unique factorisation

2.1 Prime numbers

2.2 Unique factorisation

2.3 Infinitude of primes

3 Congruences and modular arithmetic

3.1 Congruences

3.2 Modular arithmetic

3.3 Primes in congruence classes

3.4 The Chinese remainder theorem

4 The group of units mod \(m\)

4.1 Units modulo \(m\) and the \(\varphi\) function

4.2 Primitive roots

5 Computing in \(U_n\) and RSA cryptography

5.1 Powers mod \(n\)

5.2 Polynomial vs. exponential time

5.3 Public key cryptography

5.4 The RSA cryptosystem

6 Quadratic residues

6.1 Reducing to the prime case

6.2 QRs modulo primes

7 The reciprocity law

7.1 The statement

7.2 Gauss’ Lemma

7.3 Eisenstein’s lemma and the final proof

8 Gaussian integers

8.1 Definitions

8.2 Euclidean division

8.3 Gaussian primes

8.4 Euclidean rings

8.5 The Eisenstein integers

9 Arithmetic in number fields

9.1 Algebraic integers

9.2 Number fields

10 Ideals in number fields

10.1 Ideals

10.2 Factoring ideals

10.3 The class group

10.4 Cyclotomic fields, and Fermat’s Last Theorem

11 P-adic numbers

11.1 Review of metric spaces

11.2 The \(p\)-adic metric

11.3 Building the completion

11.4 The \(p\)-adic integers \(\mathbb{Z}_p\)

11.5 P-adic numbers as “power series”

12 Equations in \(\mathbb{Z}_p\) and Hensel’s lemma

12.1 Roots of polynomials

12.2 Explicitly constructing solutions

12.3 P-adic logarithms and the structure of \(\mathbb{Z}_p^\times\)

12.4 Local-to-global principles