gcds

GCDs, short for greatest common divisors, are the largest positive integers that divide each member of a given set of integers without leaving a remainder. For two integers a and b, it is denoted gcd(a, b). For more than two numbers, gcd(a1, a2, ..., an) is defined by repeatedly taking gcds of pairs.

The gcd has several basic properties. It is nonnegative and symmetric: gcd(a, b) = gcd(b, a). It is associative, so gcd(a, b, c) = gcd(gcd(a, b), c). For any integer a, gcd(a, 0) = |a|, and gcd(a, b) = gcd(|a|, |b|). Two integers are called coprime if gcd(a, b) = 1, meaning they share no prime factors in common.

GCDs are most efficiently computed via the Euclidean algorithm. This method uses the identity gcd(a, b) = gcd(b, a mod b) with gcd(a, 0) = |a|, iterating until a remainder of zero is obtained. The process runs in time proportional to the number of digits of the inputs. An alternative view is through prime factorization: the gcd consists of the common prime factors with the smallest exponents, though this is typically less efficient for large numbers.

Example: gcd(48, 18) = 6, since 6 divides both and is the largest such divisor. gcd(14, 21) = 7, and gcd(6, 10) = 2.

Applications of GCDs include simplifying fractions, solving linear Diophantine equations, and checking coprimality in modular arithmetic and cryptographic algorithms. Bézout’s identity states that gcd(a, b) is the smallest positive integer expressible as ax + by for integers x and y, reflecting the gcd’s central role in linear combinations.