Greatest Common Divisor

The greatest common divisor of two integers is the largest positive integer that divides both with no remainder. Euclid's algorithm computes it in logarithmic time by iterated remainders: GCD(a, b) = GCD(b, a mod b), terminating when b reaches 0.

The calculator extends to any number of inputs — GCD(a, b, c) = GCD(GCD(a, b), c) — and uses BigInt for arbitrary precision.

Euclid described the algorithm in Elements (Book VII, c. 300 BCE), making it one of the oldest non-trivial algorithms still in everyday use. The recursion GCD(a, b) = GCD(b, a mod b) terminates when b = 0; at that point a is the answer. Worst-case input is consecutive Fibonacci numbers: GCD(F_n, F_n+1) requires n iterations, which means the algorithm runs in O(log min(a, b)) time. For two 1000-digit numbers, fewer than 5000 modulo operations suffice. The binary GCD variant (Stein's algorithm) replaces division with bit shifts and subtraction, which can be faster on hardware lacking efficient modulo. The extended Euclidean algorithm additionally produces Bezout coefficients x, y satisfying ax + by = GCD(a, b) — the basis for modular inverse computation in RSA.

A worked example: GCD(252, 105). Iteration 1: 252 mod 105 = 42, so GCD(252, 105) = GCD(105, 42). Iteration 2: 105 mod 42 = 21, GCD(105, 42) = GCD(42, 21). Iteration 3: 42 mod 21 = 0, terminate. Answer: 21. Verifying: 252 = 21 × 12, 105 = 21 × 5, both divisions exact, and no larger integer divides both. For multiple inputs, GCD(252, 105, 168) = GCD(GCD(252, 105), 168) = GCD(21, 168) = 21. The associativity of GCD means input order doesn't change the result.

Limitations: the calculator works with integers; for floating-point inputs, GCD is undefined unless you scale to a common denominator first. Negative inputs are taken absolute by convention — GCD is defined as a non-negative integer. The edge case GCD(0, 0) is conventionally 0 but some definitions leave it undefined; the calculator returns 0 to follow the most common convention. For very large inputs (10,000+ digits), Euclid's algorithm remains efficient but the modulo operations themselves become noticeable; modern crypto libraries use further optimizations (Lehmer's GCD, half-GCD) at extreme scale.