Number theory

About the course

Divisibility and the Euclidean algorithm, Bezout's identity and Diophantine equations, factorization and divisor functions. Congruences, the inverse modulo m, fast exponentiation, the Chinese remainder theorem. The theorems of Fermat, Euler and Wilson, the Fermat test and Carmichael numbers. Primes: the sieve, the distribution x / ln x, Legendre's formula. Orders and primitive roots, quadratic residues and the reciprocity law, continued fractions, Pell's equation and RSA. A continuation of the number theory block of discrete mathematics.

Course program: 32 lessons

Divisibility and the Euclidean algorithm

  1. Divisibility and division with remainder
  2. GCD and the Euclidean algorithm
  3. Bezout's identity
  4. Linear Diophantine equations
  5. Factorization into primes and divisors
  6. Checkpoint: divisibility and Euclid

Congruences and the Chinese theorem

  1. Congruences
  2. The inverse modulo m and the congruence ax ≡ b
  3. Fast exponentiation
  4. The Chinese remainder theorem
  5. Systems with non-coprime moduli
  6. Checkpoint: congruences and the Chinese theorem

Theorems of Fermat, Euler and Wilson

  1. Fermat's little theorem
  2. Euler's function
  3. Euler's theorem
  4. Wilson's theorem
  5. The Fermat test and Carmichael numbers
  6. Checkpoint: theorems of Fermat, Euler, Wilson

Prime numbers

  1. The sieve of Eratosthenes and the infinitude of primes
  2. The distribution of primes
  3. Primes in a factorial: Legendre's formula
  4. Checkpoint: prime numbers

Orders, primitive roots, quadratic residues

  1. The order of an element
  2. Primitive roots and the discrete logarithm
  3. Quadratic residues and the Legendre symbol
  4. The law of quadratic reciprocity
  5. Checkpoint: orders and residues

Continued fractions, Pell's equation, RSA

  1. Continued fractions
  2. Pell's equation
  3. RSA
  4. Checkpoint: continued fractions, Pell, RSA

Final test

  1. Final test in number theory