GCD & LCM calculator

The greatest common divisor (GCD), also called the highest common factor (HCF), is the largest integer that divides two or more numbers without a remainder. The least common multiple (LCM) is the smallest positive integer that all of them divide into. They are used to simplify fractions, find common denominators, schedule repeating events and solve many programming problems.

How to use it

1. Enter two or more integers.
2. Read the GCD and LCM.

The Euclidean algorithm

To find GCD(a, b), repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is 0. For GCD(84, 36): 84 mod 36 = 12, 36 mod 12 = 0, so the GCD is 12. This method is fast even for very large numbers.

From GCD to LCM

LCM(a, b) = |a × b| / GCD(a, b). For 84 and 36: 3024 / 12 = 252. For more than two numbers, apply the formula pairwise: LCM(a, b, c) = LCM(LCM(a, b), c).

Practical examples

• Simplifying fractions: 84/36 divided by the GCD 12 gives 7/3.
• Common denominators: to add 1/6 and 1/8, use the LCM of 6 and 8, which is 24.
• Repeating schedules: one job runs every 12 minutes and another every 18 minutes; they coincide every LCM(12, 18) = 36 minutes.
• Gear and tile layouts: LCM tells you when patterns repeat.

Special cases

• GCD(a, 0) = a.
• If GCD(a, b) = 1, the numbers are coprime and LCM = a × b.