GCD Calculator
Find the largest integer that divides two numbers exactly with no remainder. Use it to simplify fractions, reduce ratios, or solve number-theory problems.
About this calculator
The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. The most efficient method to compute it is the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until b = 0, at which point a is the GCD. For example, GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm runs in logarithmic time, making it practical even for very large numbers. The GCD is foundational in mathematics — it is used to simplify fractions (divide numerator and denominator by their GCD), compute the LCM, and solve Diophantine equations. The GCD of any number and 0 is that number itself.
How to use
Suppose you want to simplify the fraction 56/98. Enter 56 as the First Number and 98 as the Second Number. The calculator applies the Euclidean algorithm: GCD(56, 98) → GCD(98, 56) → GCD(56, 42) → GCD(42, 14) → GCD(14, 0) = 14. The GCD is 14, so divide both terms: 56 ÷ 14 = 4 and 98 ÷ 14 = 7. The simplified fraction is 4/7. You can also use negative integers — the calculator takes absolute values before computing.
Frequently asked questions
What is the difference between GCD and HCF?
GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are two names for exactly the same concept. Both refer to the largest integer that divides two or more numbers without a remainder. The term HCF is more common in UK and Indian curricula, while GCD is preferred in most university-level mathematics and computer science contexts. You can use either term interchangeably.
How is the GCD used to simplify fractions?
To simplify a fraction a/b, compute GCD(a, b) and then divide both the numerator and denominator by that value. The result is the fraction in its lowest terms, meaning no further reduction is possible. For example, 36/48 has GCD 12, giving 3/4. This works because dividing both parts of a fraction by the same non-zero number does not change the fraction's value.
When is the GCD of two numbers equal to 1?
When GCD(a, b) = 1, the two numbers are called coprime or relatively prime. This does not mean either number is prime — for instance, GCD(8, 9) = 1 even though neither 8 nor 9 is prime. Coprime pairs are important in cryptography (especially RSA), in computing modular inverses, and in ensuring that gear ratios or tile patterns repeat correctly. Any two consecutive integers are always coprime.