Find the GCF of several numbers using the Euclidean algorithm.
The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest positive integer that divides all of the given numbers without a remainder. The Euclidean algorithm finds it efficiently: repeatedly replace the larger number with the remainder when divided by the smaller, until the remainder is zero. The last non-zero remainder is the GCF.
Euclidean algorithm
gcd(a, b) = gcd(b, a mod b); gcd(a, 0) = a
GCF of a list
gcd(a, b, c) = gcd(gcd(a, b), c) — fold pairwise
48 = 2 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. The GCF is 6. You can verify: 48/6 = 8 and 18/6 = 3, both integers.
Simplifying fractions: 18/48 = 3/8 (divide both by GCF 6). Finding the LCD (LCM = a × b / GCF). Tiling problems: the largest square tile that fits a 48 × 18 room is 6 × 6.
Yes. GCF of a list is found by folding pairwise: gcd(48, 18, 30) = gcd(gcd(48, 18), 30) = gcd(6, 30) = 6.