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 Inverses modulo \(m\)

4.2 The group of units and the \(\varphi\) function

4.3 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 sums

7.3 Enlarging the field

7.4 The supplementary law for 2

7.5 Finding the field

8 Gaussian integers

8.1 Definitions

8.2 Euclidean division

8.3 Gaussian primes

8.4 Euclidean rings

8.5 The Eisenstein integers

8.6 Another non-Euclidean ring

9 Real quadratic fields and Pell’s equation

9.1 Setup

9.2 Pell’s equation and units

9.3 The negative Pell equation

9.4 Generalized Pell equations

10 Arithmetic in number fields

10.1 Number fields

10.2 Algebraic integers

10.3 Arithmetic with algebraic integers

10.4 Rings of integers

11 Determining the integer ring

11.1 Norm and trace

11.2 Lattices and orders

11.3 The trace dual of a lattice

11.4 Addendum: Some \(\mathbb{Z}\)-linear algebra

12 Ideals in number fields

12.1 Ideals

12.2 Factoring ideals

12.3 The class group

12.4 Cyclotomic fields, and Fermat’s Last Theorem