Topics

The course splits into seven areas. They are not equally weighted on the exam, and they are not independent — modular arithmetic underpins RSA and linear codes, and group theory quietly explains why both work.

Reading order

The pages are written to be read in this order, and later pages assume the earlier ones:

1. Logic, sets & relations — the vocabulary everything else is phrased in. Equivalence relations reappear as cosets in group theory; countability is a recurring Part C problem.
2. Number theory & cryptography — the Euclidean algorithm and its consequences: diophantine equations, modular inverses, Fermat's little theorem, RSA.
3. Combinatorics & probability — counting carefully, and the handful of standard models (permutations, stars and bars, Stirling numbers).
4. Graph theory — degrees, connectivity, Euler and Hamilton, trees, planarity.
5. Group theory — the axioms, Lagrange's theorem, cyclic groups, permutations.
6. Induction — a proof technique rather than a subject, but examined in its own right.
7. Coding theory — linear codes, which are simultaneously subgroups of \((\mathbb{Z}_2)^n\) and an application of everything above.

How the topics connect

• \(\mathbb{Z}_n\) is both a group under addition and, restricted to its units \(\mathbb{Z}_n^{\times}\), a group under multiplication. RSA is Fermat's little theorem applied to the second.
• Equivalence relations partition a set into classes. Congruence mod \(n\) is an equivalence relation, and its classes are exactly the elements of \(\mathbb{Z}_n\). Lagrange's theorem is the same idea: cosets partition a group.
• A linear code is a subgroup of \((\mathbb{Z}_2)^n\), which is why \(\lvert C \rvert\) is always a power of two — that is Lagrange's theorem again.
• Counting turns up inside graph theory (degree sums), group theory (orders of subgroups), and coding theory (how many words lie within distance \(t\)).

If a proof feels like it needs a tool you have not been given, check whether one of these connections is the intended route.