Chapter 18: Number Theory. 25 sections.
25 items
Divisibility is one of the most fundamental concepts in number theory.
The Euclidean Algorithm is one of the oldest known algorithms and remains one of the most useful.
The Euclidean Algorithm computes the greatest common divisor of two integers.
Modular arithmetic is the arithmetic of remainders.
Division is one of the most subtle operations in modular arithmetic.
Exponentiation appears constantly in number-theoretic algorithms.
Prime numbers occupy a central position in number theory.
The Sieve of Eratosthenes is the standard algorithm for generating all primes up to a limit.
Many number-theoretic algorithms become simpler once a number is expressed as a product of primes.
The Chinese Remainder Theorem is a reconstruction tool.
Euler's phi function counts how many numbers in a range are coprime to a given integer.
Many algorithms require computing enormous powers modulo an integer.
Many counting problems ask for results modulo a large number.
Many counting problems involve inclusion-exclusion.
A linear congruence is the modular analogue of a linear equation.
A Diophantine equation is an equation whose solutions must be integers.
Primitive roots describe generators of modular multiplication.
Ordinary logarithms answer the question: ```text a^x = b ```
The Miller-Rabin test is the practical standard for fast primality testing.
Primality testing tells us whether a number is prime.
Number-theoretic algorithms often look simple when written with mathematical notation.
Throughout this chapter we studied individual algorithms: - Euclidean Algorithm - Modular Arithmetic - Fast Exponentiation
Number theory algorithms often look fast because their code is short.
Number-theoretic code is compact, but its edge cases are dense.
After working through the algorithms in this chapter, it is useful to step back and assemble them into a practical toolkit.