Number Theory

Info: University module; from the Euclidean algorithm to RSA.

Number theory is the arithmetic of the integers: primes, divisibility, congruences, and the deep structure hiding behind them. It is the oldest branch of mathematics and the foundation of modern cryptography. This module builds the theory from first principles (divisibility and Bézout) to public-key encryption (RSA, Diffie–Hellman).

1. Divisibility and the Euclidean Algorithm; division algorithm, gcd, Bézout, extended Euclid
2. Primes and the Fundamental Theorem of Arithmetic; Euclid’s infinitude proof, unique factorisation, divisor counting

3. Congruences; residue classes, the ring $\mathbb{Z}/n\mathbb{Z}$, exponent reduction
4. Fermat, Euler and Wilson Theorems; exponent reduction laws, the totient, primality certificates
5. Linear Congruences and the Chinese Remainder Theorem; solvability, CRT with proof, non-coprime systems

6. Arithmetic Functions; $\varphi$, $\tau$, $\sigma$, $\mu$, multiplicativity, Möbius inversion
7. Primitive Roots and Discrete Logarithms; element orders, indices, which moduli have primitive roots

8. Quadratic Residues; Euler’s criterion, Legendre symbol, quadratic reciprocity
9. Pell’s Equation and Sums of Squares; continued-fraction solutions, two-square and four-square theorems

10. The Distribution of Primes; Bertrand, Dirichlet, the Prime Number Theorem
11. Continued Fractions; convergents, best approximations, periodic expansions
12. Number Theory and Cryptography; RSA, Diffie–Hellman, ElGamal

Comfort with proof by induction and contradiction. Everything else is built in-module from the division algorithm onward.

• Computation: Euclidean algorithm, modular exponentiation, CRT reconstructions
• Proof: Euclid’s lemma, Fermat and Euler theorems, CRT uniqueness, quadratic reciprocity
• Applications: linear congruence systems, primality testing, RSA and Diffie–Hellman

• Number Theory Flashcards
• Number Theory Practice Problems
• Probability and Statistics