GCF Calculator
Find the greatest common factor of two or more numbers with prime factorization and Euclidean algorithm steps.
What Is the Greatest Common Factor?
The greatest common factor (GCF), also known as the greatest common divisor (GCD), of two or more integers is the largest positive integer that divides each of them without a remainder. For example, the GCF of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
How to Calculate the GCF
There are two common methods:
- Prime factorization: Write the prime factorization of each number, then take the lowest power of each prime that appears in all factorizations and multiply them together.
- Euclidean algorithm: Repeatedly replace the larger number with the remainder of dividing the larger by the smaller. When the remainder reaches zero, the last non-zero remainder is the GCF.
For example, to find the GCF of 12, 18, and 24: their prime factorizations are 12 = 2² × 3, 18 = 2 × 3², and 24 = 2³ × 3. Take the lowest power of each common prime: 2¹ × 3¹ = 6. So GCF(12, 18, 24) = 6.
The Euclidean Algorithm Explained
The Euclidean algorithm is an efficient method for computing the GCF of two numbers. To find GCF(a, b) where a > b: divide a by b and find the remainder r. Then replace a with b and b with r, and repeat. When the remainder becomes zero, the last non-zero remainder is the GCF. For example, GCF(48, 18): 48 ÷ 18 = 2 remainder 12; 18 ÷ 12 = 1 remainder 6; 12 ÷ 6 = 2 remainder 0. So the GCF is 6. The calculator shows each step of this process.
Real-World Uses of the GCF
- Simplifying fractions: Divide the numerator and denominator by their GCF to reduce a fraction to its simplest form.
- Dividing quantities: Split a group of items into equal-sized groups with no leftovers — the GCF gives the largest possible group size.
- Number theory: The GCF is fundamental in modular arithmetic, Diophantine equations, and cryptography (RSA).
- Tiling and packing: Find the largest square tile that fits evenly into a rectangular area.
GCF vs LCM
The GCF and LCM (Least Common Multiple) are closely related. The GCF is the largest number that divides all given numbers, while the LCM is the smallest number they all divide into. They are connected by the formula: GCF(a, b) × LCM(a, b) = a × b. This calculator shows both values so you can see the relationship.
Frequently Asked Questions
The GCF (Greatest Common Factor), also called the GCD (Greatest Common Divisor), is the largest positive integer that divides each of the given numbers without a remainder. For example, the GCF of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
The GCF can be found using prime factorization (take the lowest power of each common prime) or the Euclidean algorithm (repeatedly replace the larger number with the remainder of dividing the larger by the smaller until the remainder is zero). The calculator shows both methods.
Yes. Enter any number of comma-separated values and the calculator finds the GCF of all of them. The GCF of multiple numbers is found by iteratively computing GCF(a, b) and then GCF(result, next number).