Greatest Common Factor
The greatest common factor (GCF) is the largest number that divides evenly into two or more numbers.
Formula
\text{GCF}(a,b) = \text{product of shared prime factors with minimum exponents}
Definition
The greatest common factor (GCF) of two or more numbers is the biggest number that divides into all of them evenly, also called the greatest common divisor (GCD). It can be found by listing factors, by prime factorization (taking the minimum exponent for each shared prime), or by the Euclidean algorithm, $\text{GCF}(a,b) = \text{GCF}(b, a \bmod b)$. Algebraically, $\text{GCD}(a,b)$ is the generator of the ideal $a\mathbb{Z} + b\mathbb{Z}$ in $\mathbb{Z}$, equal to $\min\{ax + by : x,y \in \mathbb{Z}, ax+by > 0\}$; Bezout's identity guarantees integers $x,y$ exist such that $ax + by = \text{GCD}(a,b)$, and GCD generalizes to any Euclidean domain or principal ideal domain.
Example
GCF of $12$ and $18$: factors of $12$ are $1,2,3,4,6,12$, factors of $18$ are $1,2,3,6,9,18$, and the greatest common one is $6$, useful for simplifying $12/18$ to $2/3$. $\text{GCF}(48, 36)$: $48 = 2^4 \times 3$, $36 = 2^2 \times 3^2$, so $\text{GCF} = 2^2 \times 3 = 12$, matching the Euclidean chain $\text{GCF}(48,36) = \text{GCF}(36,12) = \text{GCF}(12,0) = 12$. The Bezout coefficients for $\text{GCD}(48,36) = 12$ are $12 = 48(1) + 36(-1)$, found by the extended Euclidean algorithm, essential for computing modular inverses in cryptography.
Key Insight
The GCF is useful for simplifying fractions. The Euclidean algorithm is one of the oldest known algorithms (Euclid, ~300 BCE) and one of the most efficient, running in $O(\log(\min(a,b)))$ steps. In any PID, GCD is defined via the ideal $aR + bR$; for Gaussian integers $\mathbb{Z}[i]$, $\text{GCD}(1+i, 3) = 1+i$, since $|1+i|^2 = 2$ divides into the factorizations of $3$ in a compatible way.