GCF Calculator
Calculate the greatest common factor (GCF) of two numbers using the Euclidean algorithm. Free online GCF calculator with step-by-step division steps, LCM calculation, and interactive comparison charts. Ideal for students and teachers.
About This Calculator
The GCF (Greatest Common Factor) Calculator finds the largest positive integer that divides two numbers without a remainder. Also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), this value is fundamental in number theory, fraction simplification, ratio reduction, and many areas of mathematics.
This calculator uses the Euclidean algorithm, an ancient and highly efficient method for computing the GCF. The algorithm works by repeatedly applying the modulo operation: divide the larger number by the smaller one, replace the larger number with the remainder, and repeat until the remainder is zero. The last non-zero divisor is the GCF. The calculator also computes the Least Common Multiple (LCM) using the relationship GCF(a, b) × LCM(a, b) = a × b, giving you both fundamental number theory values at once.
Each calculation displays a complete step-by-step breakdown showing every division step and remainder, making it easy to follow the Euclidean algorithm in detail. An interactive bar chart visualizes the remainder progression through each algorithm step, and a comparison view shows the relative sizes of the GCF and LCM results.
How to use
Enter two positive integers in the input fields and click "Calculate GCF". The result panel shows the GCF, the LCM, and the complete step-by-step Euclidean algorithm trace. Use the chart toggle to switch between a visual representation of the algorithm steps and a GCF vs LCM comparison bar chart.
Applications
GCF calculations are used in many real-world scenarios: simplifying fractions to their lowest terms, dividing items into equal groups, determining the largest square tile size for flooring, synchronizing repeating events, and solving problems in cryptography and computer science algorithms.
Frequently Asked Questions
What is the greatest common factor (GCF)?
The greatest common factor (GCF), also called the greatest common divisor (GCD) or highest common factor (HCF), 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 does the Euclidean algorithm find the GCF?
The Euclidean algorithm repeatedly divides the larger number by the smaller number and replaces the larger number with the remainder. This process continues until the remainder is zero. The last non-zero remainder is the GCF. For example, GCF(48, 72): 72 mod 48 = 24, 48 mod 24 = 0, so GCF = 24.
Can I calculate the LCM alongside the GCF?
Yes, this calculator also computes the least common multiple (LCM) alongside the GCF. The relationship between GCF and LCM is: GCF(a, b) × LCM(a, b) = a × b. So once the GCF is found, the LCM is calculated by dividing the product of the two numbers by their GCF.
What is the GCF of 8 and 12?
The GCF of 8 and 12 is 4. The factors of 8 are 1, 2, 4, and 8. The factors of 12 are 1, 2, 3, 4, 6, and 12. The common factors are 1, 2, and 4, and the greatest of these is 4.
What is the GCF of 24 and 36?
The GCF of 24 and 36 is 12. Using the Euclidean algorithm: 36 mod 24 = 12, then 24 mod 12 = 0, so the GCF is 12.
What is the GCF of 30 and 54?
The GCF of 30 and 54 is 6. The prime factors of 30 are 2 × 3 × 5, and the prime factors of 54 are 2 × 3 × 3 × 3. The common prime factors are 2 and 3, so the GCF is 2 × 3 = 6.
What happens if I enter 0 or a negative number?
This calculator accepts positive integers greater than zero. The GCF is defined only for positive integers, and entering zero or negative values will show a validation error. For GCF(0, n), the result is n, but this calculator focuses on the common use case of positive integer pairs.
How is the GCF different from the 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 evenly. For example, for 48 and 72: GCF is 24 (largest divisor), LCM is 144 (smallest multiple). They are related by the formula GCF × LCM = product of the two numbers.