GCD and LCM Calculator

GCD & LCM Calculator

— GCD (Greatest Common Divisor)
— LCM (Least Common Multiple)

GCD and LCM Calculator – Explained

This free online GCD and LCM calculator computes both the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of any two positive integers simultaneously. It also displays the step-by-step Euclidean algorithm so you can understand exactly how the GCD was found.

What Is GCD (Greatest Common Divisor)?

The Greatest Common Divisor — also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides both numbers without leaving a remainder. For example, GCD(48, 18) = 6 because 6 is the largest number that divides both 48 and 18 evenly.

GCD is calculated using the Euclidean Algorithm, one of the oldest algorithms in mathematics (attributed to Euclid, ~300 BC). It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.

What Is LCM (Least Common Multiple)?

The Least Common Multiple is the smallest positive integer that is divisible by both numbers. For example, LCM(4, 6) = 12 because 12 is the smallest number that both 4 and 6 divide into evenly. Once GCD is known, LCM can be calculated efficiently: LCM(A, B) = (A × B) / GCD(A, B).

Practical Uses of GCD and LCM

  • Simplifying fractions: Divide both numerator and denominator by their GCD. 18/24 → divide by GCD(18,24)=6 → 3/4.
  • Adding fractions: Use LCM as the common denominator. To add 1/4 + 1/6, use LCM(4,6)=12: 3/12 + 2/12 = 5/12.
  • Scheduling: Two events repeating every A and B days will coincide again in LCM(A,B) days.
  • Gear ratios: Engineers use LCM to find when gear teeth mesh again after one rotation.
  • Music: Beat frequencies and rhythm patterns use LCM to find when cycles align.

The Euclidean Algorithm in Detail

For GCD(48, 18): 48 = 18 × 2 + 12 → 18 = 12 × 1 + 6 → 12 = 6 × 2 + 0. The last non-zero remainder is 6, so GCD(48, 18) = 6. The calculator shows every step of this process.

Frequently Asked Questions

What is the difference between GCD and LCM?
GCD is the largest number that divides both inputs, while LCM is the smallest number that both inputs divide into. GCD is always ≤ the smaller of the two numbers; LCM is always ≥ the larger.
What is GCD(A, B) when one number is a multiple of the other?
If B is a multiple of A, then GCD(A, B) = A. For example, GCD(6, 18) = 6 because 6 divides 18 perfectly. Correspondingly, LCM(6, 18) = 18.
Can GCD or LCM be calculated for more than two numbers?
Yes. For three numbers, GCD(A, B, C) = GCD(GCD(A, B), C). The same chaining applies to LCM. This tool handles two numbers; chain the results manually for more.
What is GCD of two coprime numbers?
Two numbers are coprime (or relatively prime) if their GCD is 1. For example, GCD(8, 15) = 1. In this case, LCM(8, 15) = 8 × 15 = 120, the product of the two numbers.
Is HCF the same as GCD?
Yes. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) and GCF (Greatest Common Factor) are all the same concept, just different names used in different countries and curricula.