Greatest Common Factor
Find the greatest common factor (GCF) of two numbers using the Euclidean algorithm with step-by-step breakdown and LCM. Free number theory calculator for students and teachers.
About This Calculator
The Greatest Common Factor (GCF) calculator, also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) calculator, finds the largest positive integer that divides two given numbers without leaving a remainder. This fundamental number theory tool is essential for students learning fraction simplification, algebra, and divisibility concepts, as well as for teachers preparing lesson materials and anyone working with ratios or proportions.
Our calculator uses the Euclidean algorithm, one of the oldest and most efficient algorithms in mathematics. It works by repeatedly applying division: given two numbers A and B (A > B), compute A ÷ B and take the remainder R, then continue with B and R until the remainder reaches zero. The last non-zero remainder is the GCF. The calculator also computes the Least Common Multiple (LCM) using the relationship GCF x LCM = A x B, and displays every step of the Euclidean algorithm for educational verification.
For example, to find the GCF of 48 and 72: 72 ÷ 48 = 1 remainder 24, then 48 ÷ 24 = 2 remainder 0. The GCF is 24, meaning 24 is the largest number that divides both 48 and 72 evenly. The LCM of 48 and 72 is 144, and indeed 24 x 144 = 3456 = 48 x 72.
How to Use
Enter any two positive integers in the input fields and click "Calculate GCF." The calculator instantly shows the GCF, LCM, and a step-by-step breakdown of the Euclidean algorithm. The chart visualizes each algorithmic step or compares GCF against LCM. You can share your results using the generated URL.
Regional Notes
This calculator uses standard mathematical notation and works the same worldwide. The GCF is known by different names depending on region: GCF (Greatest Common Factor) is common in the US, GCD (Greatest Common Divisor) is used internationally and in computer science, HCF (Highest Common Factor) is prevalent in India and the UK, and HCD (Highest Common Divisor) is used in some European countries. All terms refer to the same mathematical concept.
Frequently Asked Questions
What is the greatest common factor?
The greatest common factor (GCF), also known as the greatest common divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCF of 48 and 72 is 24 because 24 is the largest number that divides both evenly.
How do you calculate the greatest common factor using the Euclidean algorithm?
The Euclidean algorithm repeatedly divides the larger number by the smaller and takes the remainder. Replace the larger number with the remainder and repeat until the remainder is zero. The last non-zero remainder is the GCF. For example, for 48 and 72: 72 ÷ 48 = 1 remainder 24, then 48 ÷ 24 = 2 remainder 0, so GCF = 24.
What is the difference between GCF and LCM?
The GCF (greatest common factor) is the largest number that divides both numbers, while the LCM (least common multiple) is the smallest number that both numbers divide into. For any two numbers a and b, GCF x LCM = a x b. For example, for 48 and 72: GCF = 24, LCM = 144, and 24 x 144 = 48 x 72 = 3456.
Can the greatest common factor be found for more than two numbers?
Yes, the GCF of multiple numbers can be found by computing the GCF pairwise: GCF(a, b, c) = GCF(GCF(a, b), c). Our calculator handles two numbers at a time, but you can apply this method sequentially for any set of numbers.
Is the greatest common factor calculator free to use?
Yes, all calculators on Calculy are completely free to use with no registration or login required. You can also share your calculations via URL.
What is the GCF of 0 and any number?
The GCF of 0 and any non-zero number is the non-zero number itself. This is because every number divides 0, so the largest common divisor is the other number. For example, GCF(0, 48) = 48.
How is the greatest common factor used in simplifying fractions?
To simplify a fraction, divide both the numerator and denominator by their GCF. For example, to simplify 48/72, divide both by the GCF of 24 to get 2/3. This gives the fraction in its simplest form in one step.
What are some real-world applications of the GCF?
GCF is used in everyday math for simplifying fractions, dividing items into equal groups (e.g., splitting 48 apples and 72 oranges into identical gift baskets), ratio problems, music theory (finding common note intervals), and computer science algorithms like cryptography.