GCF Calculator (Greatest Common Factor)
Find the greatest common factor of any set of numbers, with step-by-step Euclidean algorithm and prime factorizations.
➗ What is the Greatest Common Factor?
The greatest common factor (GCF) of two or more integers is the largest positive integer that divides each of them without leaving a remainder. For example, GCF(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 exactly. The GCF is also called the greatest common divisor (GCD) or highest common factor (HCF) depending on the country and context, but all three names refer to the same mathematical quantity.
GCF appears in many practical situations. Simplifying fractions requires dividing numerator and denominator by their GCF: the fraction 24/36 simplifies to 2/3 by dividing both by GCF(24, 36) = 12. Dividing quantities equally uses GCF to find the largest group size with no remainder: if you have 24 apples and 36 oranges and want equal bags with both fruits in each bag, GCF(24, 36) = 12 tells you the maximum number of bags possible. Tiling and measurement problems use GCF to find the largest unit that fits exactly into multiple dimensions.
There are two standard methods to find the GCF. The Euclidean algorithm repeatedly divides the larger number by the smaller and replaces the larger with the remainder, until the remainder is 0. The last non-zero remainder is the GCF. The prime factorization method decomposes each number into prime factors and takes the product of shared primes using the lowest exponent. The Euclidean algorithm is faster for large numbers because it avoids full factorization.
A closely related value is the Least Common Multiple (LCM), which is the smallest positive integer divisible by all input numbers. GCF and LCM are linked by the formula: GCF(a, b) × LCM(a, b) = a × b. This means knowing GCF immediately gives LCM for two numbers. This calculator displays both values and shows the full Euclidean algorithm derivation so you can verify or learn the process step by step.
📐 Formula
📖 How to Use This Calculator
Steps
💡 Example Calculations
Example 1 — GCF of 48 and 18
Find GCF(48, 18) using the Euclidean algorithm
Example 2 — Simplify the fraction 36/60
Use GCF to reduce 36/60 to lowest terms
Example 3 — GCF of three numbers: 12, 18, 24
Find GCF(12, 18, 24) by applying GCF iteratively
Example 4 — Coprime numbers: GCF of 35 and 48
Show that 35 and 48 share no common factor
❓ Frequently Asked Questions
🔗 Related Calculators
What is the greatest common factor (GCF)?
The greatest common factor (GCF) of two or more integers is the largest integer that divides all of them without a remainder. For example, GCF(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 exactly. GCF is also called GCD (Greatest Common Divisor) or HCF (Highest Common Factor).
How do you find the GCF using the Euclidean algorithm?
Divide the larger number by the smaller and take the remainder. Replace the larger with the smaller and the smaller with the remainder. Repeat until the remainder is 0. The last non-zero remainder is the GCF. Example: GCF(48, 18): 48 = 2 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. GCF = 6.
What is the difference between GCF, GCD, and HCF?
GCF (Greatest Common Factor), GCD (Greatest Common Divisor), and HCF (Highest Common Factor) all mean the same thing: the largest integer that divides a set of numbers exactly. GCF and HCF are common in US and UK elementary math respectively; GCD is standard in university-level number theory and computer science.
How do you find the GCF using prime factorization?
Write each number as a product of prime factors. Identify the primes shared by all numbers. Multiply the shared primes using the lowest exponent for each. Example: GCF(12, 18): 12 = 2² × 3; 18 = 2 × 3². Shared primes: 2 (min exp 1) and 3 (min exp 1). GCF = 2¹ × 3¹ = 6.
What is GCF(12, 18)?
GCF(12, 18) = 6. Using the Euclidean algorithm: 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. GCF = 6. Using prime factorization: 12 = 2² × 3 and 18 = 2 × 3². Common factors with lowest exponents: 2¹ × 3¹ = 6.
What is GCF used for in real life?
GCF has several practical uses. Simplifying fractions: divide numerator and denominator by GCF to reach lowest terms. Dividing objects into equal groups: GCF(24, 36) = 12 means 24 apples and 36 oranges can be divided into 12 equal bags with no leftovers. Tiling rooms: the largest square tile that fits both 360 cm and 480 cm dimensions is GCF(360, 480) = 120 cm.
How do you find the GCF of three or more numbers?
Apply the Euclidean algorithm iteratively. Find GCF of the first two numbers, then find GCF of that result with the third number, and so on. For GCF(12, 18, 24): GCF(12, 18) = 6; GCF(6, 24) = 6. So GCF(12, 18, 24) = 6.
What is the relationship between GCF and LCM?
For any two positive integers a and b: GCF(a, b) × LCM(a, b) = a × b. This means once you know the GCF, you can find the LCM without additional computation: LCM(a, b) = a × b / GCF(a, b). For example: a = 12, b = 18; GCF = 6; LCM = (12 × 18) / 6 = 216 / 6 = 36.
What does it mean when GCF equals 1?
When GCF(a, b) = 1, the numbers are called coprime or relatively prime. They share no common factor other than 1. For example, GCF(8, 15) = 1 because 8 = 2³ and 15 = 3 × 5 share no prime factors. Coprime numbers are important in fractions (already in lowest terms) and in modular arithmetic.
What is the GCF of two consecutive numbers?
The GCF of any two consecutive integers n and n+1 is always 1. They are always coprime. Proof: any divisor d of n also divides (n+1 - n) = 1, so d = 1. For example, GCF(7, 8) = 1; GCF(100, 101) = 1. This is why consecutive integers cannot be reduced in a fraction.
How is the Euclidean algorithm used in computer science?
The Euclidean algorithm is one of the oldest efficient algorithms and runs in O(log(min(a,b))) time. It is used in RSA encryption to find modular inverses, in fraction simplification, in computing modular arithmetic for cryptographic operations, and as a benchmark problem in algorithm courses. Its time complexity makes it practical for numbers with hundreds of digits.