Loading calculator...
Loading calculator...
Find the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm with full step-by-step working. Also calculates LCM.
Euclidean Algorithm:
GCD(a, b) = GCD(b, a mod b)
Repeat until remainder = 0; GCD is the last non-zero remainder.
LCM(a, b) = (a × b) / GCD(a, b)
Fraction simplification: a/b = (a/GCD) / (b/GCD)
The Greatest Common Divisor (GCD), also called Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides both numbers evenly. For example, GCD(12, 8) = 4.
The Euclidean algorithm finds GCD by repeatedly dividing: GCD(a, b) = GCD(b, a mod b). It terminates when the remainder is 0, and the last non-zero remainder is the GCD. It is very efficient even for large numbers.
To simplify a fraction a/b, divide both numerator and denominator by GCD(a, b). For example, 12/18: GCD = 6, so 12/18 = 2/3. This gives the fraction in its lowest terms.
For two positive integers: GCD(a, b) × LCM(a, b) = a × b. This means once you have the GCD, you can find the LCM instantly: LCM = (a × b) / GCD.
When GCD(a, b) = 1, the numbers are called coprime or relatively prime. They share no common factors other than 1. For example, GCD(9, 14) = 1. Coprime pairs are important in modular arithmetic and cryptography.