Number Theory

Divisibility, congruences and reciprocity, proved from the ground up

About this course

A proof-based course from divisibility and congruences through finite multiplicative structure, arithmetic functions, quadratic reciprocity, continued fractions, Pell equations, Gaussian integers and prime distribution.

What you will be able to do

  • Prove results on divisibility and unique factorisation, and solve linear Diophantine equations
  • Solve congruences and systems of congruences with the Chinese remainder theorem
  • Use Fermat's and Euler's theorems, orders and primitive roots, and explain the arithmetic behind RSA
  • Evaluate quadratic residues with Gauss's lemma and prove quadratic reciprocity
  • Solve Pell equations with continued fractions and decide which integers are sums of two squares

What this course covers

  • Congruence as equivalence relation and residue classes
  • Well-definedness of modular addition and multiplication
  • Exact cancellation theorem and the multiplication map
  • Modular inverses and the unit criterion
  • Solving linear congruences: existence, count, and construction
  • Applications: prime moduli, impossibility proofs, and digit-sum tests
  • Arithmetic functions and multiplicativity
  • Divisor counting and summing via exponent coordinates
  • Totient multiplicativity via Chinese Remainder Theorem
  • GCD partition and the divisor sum identity for phi
  • Dirichlet convolution: structure and multiplicativity preservation
  • Divisibility and integer combinations
  • Division with remainder (existence and uniqueness)
  • Euclid's algorithm and its correctness
  • Bézout's identity and the two-part GCD certificate
  • Coprime cancellation and its proof via Bézout
  • Gaussian integers: definition and geometry
  • Norm: definition and multiplicativity
  • Units and associates
  • Gaussian Euclidean division theorem
  • GCD and Bézout identity for Gaussian integers
  • Irreducible equals prime in the Gaussian integers
  • Unique factorisation into Gaussian primes
  • Continued fraction digit extraction algorithm
  • Continued fraction notation and finite evaluation
  • Euclidean algorithm connection and termination for rationals
  • Canonical form and uniqueness of finite expansions
  • Convergents and the numerator–denominator recurrence
  • Determinant (cross-product) identity and its consequences
  • Exact error formula, alternating sides, and convergence for irrationals
  • Integer solution existence via GCD criterion
  • Extended Euclidean algorithm for a particular solution
  • Complete family of integer solutions and proof of completeness
  • Non-negativity constraints and the feasible integer interval
  • Largest impossible value theorem for two coprime denominations
  • Signed subset cancellation and the Möbius function
  • Multiplicativity of the Möbius function
  • Fundamental divisor sum identity and Möbius inversion
  • Coprimality indicator and counting coprime integers and pairs
  • Square-free indicator and its exact summatory formula
  • Uniqueness of inversion and lecture synthesis
  • Two error measures for rational approximation
  • Dirichlet / pigeonhole existence theorem
  • Determinant identity and integer coordinates
  • Best second-kind approximation theorem
  • First-kind (ordinary distance) optimality corollary
  • Legendre's recognition criterion and its sharpness
  • Rational uniqueness from a certified short interval
  • Geometric and algebraic setup for sums of two squares
  • Product identity for sums of two squares
  • Obstruction from primes congruent to 3 mod 4
  • Wilson's congruence and a square root of −1 mod P
  • Gaussian GCD extraction of a prime representation
  • Complete classification theorem for sums of two squares
  • Counting formula for signed ordered representations
  • CRT for coprime moduli: existence and uniqueness
  • Selector (Bézout) construction for two moduli
  • General CRT for k pairwise coprime moduli via selectors
  • CRT for non-coprime moduli: compatibility and LCM period
  • Pairwise compatibility suffices for finite families of integer congruences
  • Residue class vs. single integer: range restriction
  • Units modulo N and Euler's totient function
  • Multiplication by a unit permutes the unit set
  • Euler's theorem and Fermat's little theorem
  • Converse failure of Fermat and binary exponentiation
  • Wilson's theorem: prime characterisation via (p−1)! ≡ −1
  • Fundamental Theorem of Arithmetic: Statement and Scope
  • Existence of Prime Factorization via Well-Ordering
  • Euclid's Lemma and the Uniqueness Proof
  • Prime Exponent Profiles: Multiplication, Divisibility, GCD, and LCM
  • Counting Divisors, Perfect Powers, and Irrationality via Exponent Profiles
  • Prime Testing, the Sieve, and the Square Root Bound
  • Restricted Multiplicative Systems and the Limits of Uniqueness
  • The integer quadratic ring and conjugation
  • Norm: definition, multiplicativity, and units
  • Generating solutions by multiplying a seed
  • Dirichlet approximation and bounded norms
  • Double pigeonhole argument and existence of a norm-one solution
  • Fundamental solution and classification of all solutions
  • Continued fractions as a search algorithm for the fundamental solution
  • Euclid's Infinitude of Primes Argument
  • Divergence of the Harmonic Series
  • Divergence of the Sum of Prime Reciprocals
  • Explicit Lower Bound on Prime Counts via Binomial Coefficients
  • Upper Bound on θ(x) and Zero Natural Density of Primes
  • Infinitude of Primes in Residue Classes mod 4
  • Unbounded Prime Gaps and the Sieve of Eratosthenes
  • Quadratic residues and the squaring map
  • The Legendre symbol
  • Euler's criterion and multiplicativity
  • Gauss's lemma: signed-permutation criterion
  • Supplementary laws: squares of −1 and 2
  • Square-root construction and domain limits
  • Certificates, Completeness, and Three Conclusion Types
  • Modular Square Roots via CRT and Prime Factorization
  • Non-Trivial Roots and Factor Partitioning
  • Gaussian GCDs and Norm Representations
  • Pell Equation: Minimal Seed and Complete Infinite Family
  • Rational Reconstruction from a Narrow Interval
  • Fermat Pseudoprimes and Non-Trivial Square Root Witnesses
  • Quadratic Reciprocity: Statement and Sign Cases
  • Gauss's Lemma and the Parity Bridge (Floor Sum Formula)
  • The Half-Size Rectangle and Its Lattice Points
  • Column and Row Counts as Floor Sums
  • Central Result: Proof of Quadratic Reciprocity
  • Applying Reciprocity: Reduction Procedure and Worked Examples
  • Boundary Conditions and Domain Limitations
  • Multiplicative order of a unit
  • Return theorem and collision of powers
  • Cyclic subgroups and Lagrange's theorem
  • Polynomial root bound over a prime field
  • Counting short-cycle elements; discrete logarithm preview
  • Primitive roots and cyclic groups defined
  • Coprime-order product lemma
  • Extracting prime-power order components
  • Every finite subgroup of a field's multiplicative group is cyclic
  • Certifying primitive roots and counting them
  • Solving power equations via discrete logarithms
  • Trial division and its exponential cost
  • Fermat test, compositeness witnesses, and Carmichael numbers
  • Miller-Rabin strong test and strong pseudoprimes
  • Full-order primality certificate
  • RSA correctness theorem for all message residues

Syllabus

  1. Divisibility and Primes

    1. L1 · Divisibility, Euclid and the Meaning of a Proof
    2. L2 · Linear Diophantine Equations and Integer Lattices
    3. L3 · Primes and Unique Factorization

  2. Congruences and Multiplicative Structure

    1. L4 · Congruences, Inverses and Linear Equations
    2. L5 · The Chinese Remainder Theorem
    3. L6 · Fermat, Euler and Multiplicative Symmetry
    4. L7 · Orders, Cyclic Subgroups and Polynomial Roots
    5. L8 · Primitive Roots and Discrete Logarithms
    6. L9 · Primality Tests and the Mathematics of RSA

  3. Arithmetic Functions and Quadratic Reciprocity

    1. L10 · Arithmetic Functions and Multiplicativity
    2. L11 · Mobius Inversion and Counting Coprime Objects
    3. L12 · Quadratic Residues and Gauss Lemma
    4. L13 · Quadratic Reciprocity: A Complete Proof

  4. Continued Fractions and Pell Equations

    1. L14 · Continued Fractions and Convergents
    2. L15 · Rational Approximation and Best Approximants
    3. L16 · Pell Equations and Quadratic Units

  5. Gaussian Integers, Primes and Capstone

    1. L17 · Gaussian Integers and a New Euclidean Algorithm
    2. L18 · Which Integers Are Sums of Two Squares?
    3. L19 · Infinitely Many Primes and Quantitative Questions
    4. L20 · A Number Theory Laboratory and Proof Capstone