GCD & LCM Calculator
Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of any two positive integers instantly. This calculator uses the efficient Euclidean algorithm and also shows whether the numbers are coprime.
The GCD and LCM are fundamental concepts in number theory with wide applications in mathematics, engineering, and computer science.
Greatest Common Divisor (GCD):
The GCD of two numbers is the largest positive integer that divides both numbers without a remainder. Also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF).
- The Euclidean algorithm is the most efficient method: repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD.
- Example: GCD(48, 18): 48 = 2x18 + 12, then 18 = 1x12 + 6, then 12 = 2x6 + 0. So GCD = 6.
Least Common Multiple (LCM):
The LCM of two numbers is the smallest positive integer that is divisible by both numbers.
- Formula: LCM(a, b) = (a x b) / GCD(a, b).
- Example: LCM(12, 18) = (12 x 18) / GCD(12, 18) = 216 / 6 = 36.
Key Relationship: For any two positive integers a and b: GCD(a, b) x LCM(a, b) = a x b.
These calculations are essential for simplifying fractions, finding common denominators, synchronizing periodic events, and many algorithms in computer science.