What is the GCD (greatest common divisor)?

The GCD of two or more integers is the largest positive integer that divides all of them without a remainder. For example, GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18. GCD is also called GCF (greatest common factor) or HCF (highest common factor).

What is the LCM (least common multiple)?

The LCM of two or more integers is the smallest positive integer that is divisible by all of them. For example, LCM(4, 6) = 12 because 12 is the smallest number divisible by both 4 and 6. LCM is useful for adding fractions and solving problems involving repeating cycles.

How does the Euclidean algorithm work?

The Euclidean algorithm finds the GCD by repeatedly applying: GCD(a, b) = GCD(b, a mod b) until the remainder is 0. The last non-zero remainder is the GCD. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6.

How are GCD and LCM related?

For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. This relationship allows LCM to be computed efficiently as LCM(a, b) = a × b ÷ GCD(a, b).

GCD & LCM Calculator - Greatest Common Divisor & Least Common Multiple

Greatest Common Divisor (GCD)

The GCD of two integers is the largest integer that divides both numbers without a remainder. It is also called the greatest common factor (GCF) or highest common factor (HCF). The Euclidean algorithm (developed around 300 BCE) computes it efficiently by repeatedly taking remainders: GCD(a, b) = GCD(b, a mod b).

Least Common Multiple (LCM)

The LCM is the smallest positive integer divisible by all given numbers. It is essential for adding fractions with different denominators and for scheduling problems involving repeating events. The LCM is related to the GCD by: LCM(a, b) = a × b ÷ GCD(a, b).

Using prime factorization

An alternative way to find GCD and LCM uses prime factorizations. For the GCD, take each prime that appears in all factorizations, raised to the minimum exponent. For the LCM, take each prime that appears in any factorization, raised to the maximum exponent.

Euclidean algorithm step-by-step

Step	a	b	a mod b
1	48	18	12
2	18	12	6
3	12	6	0
GCD	6 (last non-zero remainder)

Applications

Simplifying fractions: divide numerator and denominator by their GCD to reduce to lowest terms. 48/18 ÷ 6/6 = 8/3.
Scheduling: if event A repeats every 18 days and event B every 48 days, LCM = 144 gives the next day they coincide.
Music theory: polyrhythms use LCM to find when beat cycles realign - a 3-against-4 pattern realigns every LCM(3,4) = 12 beats.
Gear ratios: GCD simplifies ratio expressions; LCM finds when gear teeth realign.

Extended Euclidean algorithm

The extended Euclidean algorithm finds integers x, y such that ax + by = GCD(a, b) (Bézout's identity). This has direct applications in modular arithmetic and is the basis of the RSA encryption algorithm's key generation step, where the multiplicative inverse modulo a number is computed using the extended GCD.