Euclidean GCD
Compute greatest common divisor using repeated division.
How it works
The Euclidean Algorithm is one of the oldest known algorithms, described by Euclid around 300 BCE, yet it remains the standard method for computing the greatest common divisor (GCD) in modern software. The core insight is a divisibility invariant: gcd(a, b) = gcd(b, a mod b). Because the remainder a mod b is strictly smaller than b, the pair (a, b) shrinks with every iteration, and the algorithm is guaranteed to terminate when b reaches zero, at which point a holds the GCD.
The convergence rate is remarkably fast. By Lamé's theorem, the number of iterations is bounded by five times the number of decimal digits in the smaller input — or more precisely, O(log min(a, b)). This logarithmic complexity makes the algorithm practical even for very large integers (hundreds of digits), as used in cryptographic key generation. The iterative formulation used here avoids call-stack allocation and is straightforward to implement in any language or hardware, making it a preferred choice over the recursive form in embedded systems and safety-critical applications.
The Euclidean Algorithm is the foundation of the Extended Euclidean Algorithm, which additionally computes Bézout coefficients x and y such that ax + by = gcd(a, b). This extension is essential in modular arithmetic: it computes the modular inverse of a number, which is the central operation in RSA encryption and elliptic-curve cryptography. Beyond cryptography, the algorithm appears whenever integer ratios must be reduced to lowest terms — in font rasterizers, media decoders computing aspect ratios, and compilers performing constant folding on rational expressions.
Complexity
Visualizer
Where it's used in the real world
RSA and elliptic-curve cryptography libraries (OpenSSL, BoringSSL)
Modular inverse computation for private key generationRSA key generation requires computing the modular inverse of the public exponent e modulo φ(n). The Extended Euclidean Algorithm — a direct extension of the algorithm visualized here — computes this inverse in O(log n) steps. Every TLS handshake on the internet ultimately depends on this algorithm.
Compiler front-ends and constant-folding passes
Fraction simplification in rational constant arithmeticCompilers that support rational literals or symbolic constant folding (e.g., GHC for Haskell, Julia's type system) reduce fractions like 12/8 to 3/2 by computing gcd(12, 8) = 4 and dividing both terms. The Euclidean Algorithm is the standard primitive used in the compiler's internal arithmetic library.
Media frameworks (FFmpeg, GStreamer, Apple AVFoundation)
Aspect ratio and sample rate normalizationVideo containers store frame dimensions and sample rates as integer ratios. When transcoding or displaying media, frameworks reduce 1920/1080 → 16/9 and 44100/48000 → 147/160 using gcd() to find the canonical form. FFmpeg's av_reduce() calls gcd internally on every stream open.
Implementation
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
// Extended Euclidean — also returns Bézout coefficients
function extendedGcd(
a: number,
b: number
): { gcd: number; x: number; y: number } {
if (b === 0) return { gcd: a, x: 1, y: 0 };
const { gcd, x, y } = extendedGcd(b, a % b);
return { gcd, x: y, y: x - Math.floor(a / b) * y };
}
console.log(gcd(48, 18)); // 6
console.log(gcd(100, 75)); // 25
console.log(extendedGcd(35, 15)); // { gcd: 5, x: 1, y: -2 }