gcd (greatest common divisor)
For integers a, b (not both zero), gcd(a, b) is the largest integer d that divides both a and b. It’s unique, positive, and can be found with the ordinary Euclidean algorithm.
Modular reduction
For integer a and positive integer m, a mod m is the remainder after dividing a by m, chosen in {0, 1, …, m − 1}. Equivalently, a ≡ r (mod m) means m divides (a − r).
Modular inverse
An integer x is the inverse of a modulo m iff a · x ≡ 1 (mod m). Such an x exists ⇔ gcd(a, m) = 1. When it exists, it is unique modulo m (i.e., unique in {0, …, m − 1}).
Extended Euclidean Algorithm
Input: integers a, b. Output: integers (g, x, y) such that g = gcd(a, b) and a x + b y = g. Runs in O(log min(a, b)) time and O(1) space iteratively.