Prime Numbers Course

Lesson 1 • What Makes a Number Prime

Defines prime numbers through divisibility rules and factor counting. Anchors the chapter by establishing the core criterion all later topics depend on.

Lesson 2 • Composite Numbers and Factorization

Breaks composites into prime building blocks using factor trees and repeated division. Establishes the contrast with primes needed throughout the course.

Lesson 3 • Early Prime Examples and Patterns

Surveys the first several primes and surface-level patterns in their distribution. Builds intuition before formal theory is introduced.

Lesson 1 • GCD and LCM via Factorisation

Uses prime factorisations to compute greatest common divisors and least common multiples. Demonstrates immediate practical value of the fundamental theorem.

Lesson 2 • Proof Strategy and Key Lemmas

Walks through the proof structure using Euclid's lemma as the central tool. Develops logical reasoning skills applied throughout the course.

Lesson 3 • Statement and Meaning of the Theorem

Presents the theorem precisely and explains why uniqueness matters. Sets the conceptual foundation for all factorisation-based techniques in the chapter.

Lesson 4 • Limitations and Edge Cases

Examines where standard factorisation assumptions break down, including the role of units. Prepares students for generalised settings encountered in advanced chapters.

Lesson 1 • Miller-Rabin Primality Test

Presents the Miller-Rabin algorithm as a robust probabilistic primality test. Students learn to bound error probability and apply the test to large integers.

Lesson 2 • The Sieve of Eratosthenes

Teaches the classical sieve for generating all primes up to a bound efficiently. Introduces batch primality testing as a complement to single-number methods.

Lesson 3 • AKS Deterministic Primality Test

Surveys the AKS algorithm as the first polynomial-time deterministic primality test. Contextualises its theoretical importance versus practical use cases.

Lesson 4 • Trial Division in Depth

Refines the basic trial division approach with the square-root bound and odd-only testing. Establishes the baseline algorithm against which faster methods are compared.

Lesson 1 • Prime Gaps and Clusters

Examines the spacing between consecutive primes, including twin primes and large gaps. Connects empirical observations to open conjectures in number theory.

Lesson 2 • Prime Counting Function

Defines the prime counting function and examines its growth through tabulated data. Provides the quantitative tool used in the prime number theorem.

Lesson 3 • The Prime Number Theorem

States and interprets the prime number theorem and its logarithmic approximation. Gives students the central asymptotic result governing prime distribution.

Lesson 4 • Infinitude of Primes

Presents Euclid's proof and modern variants showing primes never run out. Establishes the infinite landscape within which distribution questions arise.

Lesson 1 • Wieferich and Wall-Sun-Sun Primes

Introduces rare prime classes defined by congruence conditions involving powers and Fibonacci numbers. Illustrates how exotic primality conditions arise from deep number theory.

Lesson 2 • Sophie Germain and Safe Primes

Defines Sophie Germain primes and their paired safe primes. Highlights their role in cryptographic protocol design covered in later chapters.

Lesson 3 • Mersenne Primes

Studies primes of the form two to the power n minus one and their necessary conditions. Connects to the Lucas-Lehmer test and the search for large primes.

Lesson 4 • Twin Primes and Prime Constellations

Defines twin primes and broader prime constellations with fixed gap patterns. Surveys the conjecture landscape and known partial results.

Lesson 1 • Fermat's Little Theorem Applied

Derives and applies Fermat's little theorem for prime moduli in computation. Enables fast modular exponentiation and inverse computation used in cryptography.

Lesson 2 • Modular Arithmetic Foundations

Reviews congruence notation, residue classes, and arithmetic operations modulo n. Establishes the algebraic framework required for all prime-modular results.

Lesson 3 • Quadratic Residues and Legendre Symbol

Defines quadratic residues modulo a prime and introduces the Legendre symbol. Provides tools for determining solvability of quadratic congruences.

Lesson 4 • Euler's Theorem and Totient Function

Extends Fermat's result to composite moduli using Euler's totient function. Broadens the toolkit for modular computation beyond prime moduli.

Lesson 1 • Security of RSA and Factoring Hardness

Analyses RSA security assumptions and known attacks based on factoring algorithms. Guides students in selecting safe key sizes and prime generation practices.

Lesson 2 • RSA Encryption and Decryption

Constructs the RSA algorithm from prime selection through key generation to message recovery. Demonstrates how prime factorisation hardness underpins public-key security.

Lesson 3 • Elliptic Curve Cryptography Basics

Introduces elliptic curves over prime fields and the elliptic curve discrete log problem. Shows how smaller primes yield equivalent security compared to RSA.

Lesson 4 • Generating Cryptographic Primes

Covers practical methods for generating large random primes suitable for cryptographic use. Integrates primality testing from earlier chapters into a production workflow.

Lesson 1 • Computational Prime Research

Surveys distributed computing projects and algorithms driving record prime discoveries. Connects theoretical knowledge to active large-scale computational efforts.

Lesson 2 • The Riemann Hypothesis and Primes

Connects the Riemann zeta function's zeros to the precise distribution of primes. Presents the hypothesis as the deepest open problem linking analysis and prime theory.

Lesson 3 • Goldbach's Conjecture

States Goldbach's conjecture and surveys computational verification and partial proofs. Illustrates how simple prime statements can resist proof for centuries.

Lesson 4 • Primes in Polynomial Sequences

Investigates whether polynomials can generate infinitely many primes and known results. Extends distribution theory to algebraically defined sequences.