GCD / LCM
Divisor and multiple calculations.
What does GCD / LCM mean?
The Greatest Common Divisor (GCD) is the largest positive integer that divides two numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of both numbers. Together, GCD and LCM are fundamental tools in number theory, used for simplifying fractions, finding common denominators, and solving problems in scheduling, engineering, and cryptography.
How to calculate GCD / LCM
GCD is calculated using the Euclidean algorithm: repeatedly divide the larger number by the smaller and take the remainder until the remainder is zero — the last non-zero remainder is the GCD. LCM is then found with the formula: LCM(a, b) = (a * b) / GCD(a, b). For example, for 24 and 36: GCD(24, 36) = 12, and LCM(24, 36) = (24 * 36) / 12 = 72.
FAQ
The Euclidean algorithm is an efficient method for finding the GCD of two integers. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until one of the numbers becomes zero. The other number at that point is the GCD. For example, GCD(48, 18): 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0, so GCD = 6.
GCD and LCM are related by the identity: GCD(a, b) * LCM(a, b) = a * b. This means if you know the GCD, you can easily compute the LCM and vice versa. This relationship holds for any two positive integers.
GCD is used to simplify fractions (divide numerator and denominator by their GCD), while LCM is used to find common denominators when adding fractions. In real life, LCM helps with scheduling (e.g., when two events with different cycles will coincide), and GCD is used in tiling problems, gear ratios, and cryptography (RSA algorithm).
Yes. To find the GCD or LCM of multiple numbers, apply the operation iteratively: GCD(a, b, c) = GCD(GCD(a, b), c), and LCM(a, b, c) = LCM(LCM(a, b), c). The same formulas and relationships apply at each step.
Two numbers are coprime (or relatively prime) when their GCD is 1 — they share no common factors other than 1. In that case, the LCM equals the product of the two numbers. For example, GCD(8, 15) = 1 and LCM(8, 15) = 120 = 8 * 15.
Related calculators
- Ratio— Relative comparison of values.
- Proportion— Equality of two ratios.
- Factorial— Product of descending integers.
- Combinations— Unordered selections.