gcd

GCD stands for greatest common divisor, the largest positive integer that divides each of two or more integers without leaving a remainder. For example, gcd(48, 18) equals 6 because 6 divides both numbers and no larger positive integer does. The gcd is defined for integers; by convention gcd(a, 0) = |a| and gcd(0, 0) is often taken as 0 or considered undefined in some contexts.

A standard method to compute the gcd of two integers is the Euclidean algorithm. It relies on the principle that gcd(a, b) = gcd(b, a mod b). Repeating this step reduces the problem until the remainder is zero; the other number at that step is the gcd. For instance, gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6. The extended Euclidean algorithm further produces integers x and y such that ax + by = gcd(a, b), providing a Bezout identity and a way to compute modular inverses when gcd(a, m) = 1.

The binary gcd algorithm, or Stein’s algorithm, computes gcd using only subtraction and division by two, exploiting binary representations to avoid division. It is often efficient in computer implementations.

GCD also generalizes beyond two integers and to polynomials over a field. The gcd of a set {a1, ..., ak} is the greatest positive integer that divides all of them. In abstract algebra, gcds exist in certain domains called gcd domains or in the ring of polynomials, where the concept mirrors the integer case.

Key properties include commutativity, associativity, and the relation gcd(a, b) = gcd(|a|, |b|). If gcd(a, b) = 1, then a and b are coprime, and a has a multiplicative inverse modulo b. GCDs are used to simplify fractions, solve Diophantine equations, and analyze divisibility and modular arithmetic.