Greatest Common Divisor (GCD) Calculator
GCD Calculator
The Greatest Common Divisor (GCD) is the largest number that divides two integers evenly. It is fundamental to number theory and practical tasks like simplifying fractions.
Conversion Formula
The Euclidean algorithm repeatedly applies: GCD(a, b) = GCD(b, a mod b). This continues until b = 0, at which point a is the GCD.
Step-by-Step Examples
48, 36 = GCD = 12
48 = 1×36 + 12, 36 = 3×12 + 0. The GCD is 12.
100, 75 = GCD = 25
100 = 1×75 + 25, 75 = 3×25 + 0. The GCD is 25.
Frequently Asked Questions
What is the GCD?
The Greatest Common Divisor (GCD) is the largest positive integer that divides both numbers without a remainder. Also called HCF (Highest Common Factor).
How does the Euclidean algorithm work?
Repeatedly replace the larger number with the remainder of dividing it by the smaller number until the remainder is zero. The last non-zero remainder is the GCD.
What is the GCD of two prime numbers?
The GCD of two different prime numbers is always 1 because primes have no common factors other than 1.
What if one number is zero?
GCD(a, 0) = a. Any number divides zero, so the GCD is the non-zero number.
How is GCD used in fractions?
Divide both numerator and denominator by their GCD to simplify a fraction. For example, 48/36 ÷ 12/12 = 4/3.