Greatest Common Factor
ArithmeticThe 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. It is also called the greatest common divisor (GCD).
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$. Common factors: $1, 2, 3, 6$. The greatest is $6$.
Key Insight
The GCF is useful for simplifying fractions: to reduce $12/18$, divide both by $\text{GCF}(12,18) = 6$ to get $2/3$.
Definition
$\text{GCF}(a,b)$ is the largest positive integer that divides both $a$ and $b$. It can be found by listing factors, using prime factorization (take the minimum exponent for each shared prime), or the Euclidean algorithm: $\text{GCF}(a,b) = \text{GCF}(b, a \bmod b)$.
Example
$\text{GCF}(48, 36)$: $48 = 2^4 \times 3$, $36 = 2^2 \times 3^2$. $\text{GCF} = 2^2 \times 3 = 12$. Euclidean: $\text{GCF}(48,36) = \text{GCF}(36,12) = \text{GCF}(12,0) = 12$.
Key Insight
The Euclidean algorithm is one of the oldest known algorithms (Euclid, ~300 BCE) and one of the most efficient. It runs in $O(\log(\min(a,b)))$ steps.
Definition
$\text{GCD}(a,b)$ is the generator of the ideal $a\mathbb{Z} + b\mathbb{Z}$ in $\mathbb{Z}$: $\text{GCD}(a,b) = \min\{ax + by : x,y \in \mathbb{Z}, ax+by > 0\}$. Bezout's identity: there exist integers $x,y$ such that $ax + by = \text{GCD}(a,b)$. GCD generalizes to any Euclidean domain or principal ideal domain.
Example
Bezout coefficients for $\text{GCD}(48,36) = 12$: $12 = 48(1) + 36(-1)$. Extended Euclidean algorithm finds these coefficients, essential for computing modular inverses in cryptography.
Key Insight
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.