Greatest Common Factor Calculator
Find the GCF (greatest common divisor) of two or more numbers using the Euclidean algorithm.
Inputs
Greatest Common Factor (GCF)
6
Input Numbers
48, 18
Step by step
Inputs
= 48, 18
Euclidean step
gcd(48, 18): 48 = 2 × 18 + 12
Euclidean step
gcd(18, 12): 18 = 1 × 12 + 6
Euclidean step
gcd(12, 6): 12 = 2 × 6 + 0
GCF
= 6
How it works
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.
Formulas
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
Frequently Asked Questions
What is gcd(48, 18)?
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.
What is the GCF used for?
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.
Can I find the GCF of more than two numbers?
Yes. GCF of a list is found by folding pairwise: gcd(48, 18, 30) = gcd(gcd(48, 18), 30) = gcd(6, 30) = 6.
You might also need
- Euclidean Algorithm CalculatorCommonly used together
- Common Factor CalculatorCommonly used together
- Extended Euclidean Algorithm CalculatorCommonly used together
- Least Common Multiple CalculatorCommonly used together
- Factor CalculatorCommonly used together
- Prime Factorization CalculatorCommonly used together