calculate GCD & LCM Calculator star

How Are GCD and LCM Calculated?

The greatest common divisor (GCD) of two numbers is the largest number that divides both without a remainder. The fastest way to find it is the Euclidean algorithm, known since roughly 300 BC: divide the larger number by the smaller one, then replace the larger number with the remainder and repeat. When the remainder finally reaches 0, the last non-zero remainder is the GCD.

Worked example — GCD(48, 18): 48 = 2 × 18 + 12, then 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0. The remainder just became 0, so the divisor at that step, 6, is the GCD. No factoring into primes was needed, and the process took only three steps — that speed is exactly why the Euclidean algorithm, not trial division, is what calculators and computers use internally.

The least common multiple (LCM) is the smallest number that both originals divide into evenly. Once the GCD is known, the LCM follows directly from a single formula: LCM(a,b) = (a × b) ÷ GCD(a,b). For the same pair, LCM(48,18) = (48 × 18) ÷ 6 = 864 ÷ 6 = 144. The relationship GCD × LCM = a × b always holds for any two positive integers, which is a handy way to sanity-check an answer by hand.

For more than two numbers, the tool reduces the list pairwise: it finds GCD(a,b) first, then the GCD of that result with c, and so on; LCM works the same way, folding in one number at a time.

What You Should Know

• Fraction simplification. To reduce a fraction to lowest terms, divide numerator and denominator by their GCD. 24/36 has GCD(24,36) = 12, so it simplifies to 2/3 in one step — no guess-and-check needed.
• Common denominators. When adding fractions with different denominators, the LCM of the denominators gives the smallest common denominator to work with, keeping the numbers manageable instead of just multiplying the denominators together.
• Coprime numbers. If two numbers share no common factor other than 1 (e.g. 8 and 9), their GCD is 1 and their LCM is simply their product — GCD(8,9) = 1, LCM(8,9) = 72.
• A common mistake is assuming the GCD of three or more numbers is the GCD of just two of them; always reduce the whole list, since a factor shared by two numbers may not be shared by all.
• Real-world use. LCM answers "when do two repeating schedules line up again" (two buses leaving every 12 and 18 minutes both depart together every LCM(12,18) = 36 minutes), while GCD answers "what is the largest equal-sized group I can split things into."