Euclidean algorithm

The Euclidean algorithm computes the greatest common divisor of two integers by repeatedly replacing them with a smaller pair that has the same divisor.

Division algorithm: For integers a and positive b, there are unique integers q and r with a = bq + r and 0 ≤ r < b. Each step writes the larger input as a multiple of the smaller plus a remainder.
Extended Euclidean algorithm: An extension of the Euclidean algorithm that finds coefficients expressing the gcd as a linear combination of the inputs. It tracks coefficients through the same divisions to construct Bézout coefficients.
Elements (Euclid): Elements is Euclid's thirteen-book mathematical treatise, composed around 300 BCE. Book VII presents the procedure for finding the greatest common measure of two numbers.
Binary GCD algorithm: The binary GCD algorithm computes a greatest common divisor using parity tests, shifts, and subtraction. It replaces division with operations that can be cheaper on binary hardware.
Greatest common divisor: The greatest common divisor of integers is the largest positive integer dividing each of them. The algorithm’s invariant is that every pair has the same greatest common divisor.
Modular multiplicative inverse: A modular multiplicative inverse of a modulo n is an integer x satisfying ax ≡ 1 mod n. The extended algorithm finds the inverse exactly when a and n are coprime.
Euclid: Euclid was an ancient Greek mathematician associated with the foundational treatise Elements. The algorithm is named for the author whose Elements records its classical form.
Stein's algorithm: Stein's algorithm is a binary method for computing the greatest common divisor using powers of two and subtraction. It is another name for the binary alternative to repeated remainder division.
Euclidean lemma: If an integer divides a product of two integers and is coprime to one factor, it divides the other factor. This divisibility principle underlies the algorithm’s connection to prime factors.
RSA: RSA is a public-key cryptosystem whose security relies on the difficulty of factoring large integers. RSA key generation uses gcd computations to test whether exponents are coprime.

Linked from 31 pages