GCF

The greatest common factor (GCF), also called the greatest common divisor (GCD), of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. It is defined for nonzero integers, and when zero is involved the convention is gcd(a,0) = |a|; gcd(0,0) is treated differently in some contexts and may be considered undefined in pure number theory or defined as 0 in some programming settings.

GCF can be found by several methods. The prime factorization method identifies the common prime powers shared by the numbers and multiplies them. The Euclidean algorithm is typically more efficient: gcd(a,b) is computed as gcd(b, a mod b) and repeated until the remainder is 0, at which point the last nonzero remainder is the gcd. For more than two numbers, gcd(a,b,c) is defined recursively as gcd(gcd(a,b), c).

For example, gcd(48, 180) is 12. Prime factorizations show 48 = 2^4 × 3 and 180 = 2^2 × 3^2 × 5; the shared factors are 2^2 × 3 = 12. If a, b, and c are involved, gcd(a,b,c) = gcd(gcd(a,b), c). Properties of the GCF include commutativity and associativity, and Bezout’s identity states that gcd(a,b) is the smallest positive integer expressible as ax + by for integers x and y. The GCF is related to the least common multiple (LCM) via a*b = gcd(a,b) × lcm(a,b) for positive integers. Applications include simplifying fractions, solving Diophantine equations, and problems in modular arithmetic.