How to Calculate GCD and LCM

GCD(a, b) is the largest positive integer d such that d divides a and d divides b. Example: divisors of 48 include 1, 2, 3, 4, 6, 8, 12, 16, 24, 48; divisors of 18 include 1, 2, 3, 6, 9, 18. Shared divisors: 1, 2, 3, 6. So GCD(48, 18) = 6.

LCM(a, b) is the smallest positive integer m that is a multiple of both a and b. Multiples of 4: 4, 8, 12, 16, 20, 24… Multiples of 6: 6, 12, 18, 24… First shared multiple is 12, so LCM(4, 6) = 12.

Why both matter

• GCD reduces fractions and ratios: 48/18 → divide top and bottom by 6 → 8/3
• LCM finds common denominators: 1/4 + 1/6 needs denominator 12
• Both appear in scheduling (buses every 12 and 18 minutes meet every LCM minutes)

GCD is sometimes labeled HCF (highest common factor) — same definition. For ratio work that depends on GCD, see how to simplify a ratio to lowest terms.

The Euclidean algorithm is the standard hand method for two integers. It uses remainders:

1. Write GCD(a, b) with a ≥ b.
2. Divide a by b; let r = a mod b (remainder).
3. Replace a with b and b with r.
4. Repeat until remainder is 0. The last non-zero remainder is the GCD.

Worked example: GCD(252, 105)

• 252 = 2 × 105 + 42
• 105 = 2 × 42 + 21
• 42 = 2 × 21 + 0
• Last non-zero remainder = 21 → GCD(252, 105) = 21

Why it works

Any common divisor of a and b also divides a − qb for any integer q, so it divides the remainder. The set of common divisors never changes as you replace (a, b) with (b, r), until you hit (d, 0) and d is the GCD.

For negatives, use absolute values: GCD(−48, 18) = GCD(48, 18) = 6. GCD with 0: GCD(n, 0) = |n|.

Run Euclidean steps without arithmetic slips in the free GCD and LCM calculator when the numbers get large.

Factor each integer into primes, then combine exponents carefully.

• GCD: take each prime that appears in all numbers, with the minimum exponent.
• LCM: take each prime that appears in any number, with the maximum exponent.

Example: 84 and 90

84 = 2² × 3 × 7
90 = 2 × 3² × 5

• GCD = 2¹ × 3¹ = 6 (min exponents; 5 and 7 drop out)
• LCM = 2² × 3² × 5 × 7 = 4 × 9 × 5 × 7 = 1260

Three numbers: 12, 18, 30

12 = 2² × 3
18 = 2 × 3²
30 = 2 × 3 × 5

• GCD = 2¹ × 3¹ = 6
• LCM = 2² × 3² × 5 = 4 × 9 × 5 = 180

Prime factor trees are slower than Euclidean for two huge numbers, but they make multi-number LCM transparent and connect to fraction work when you convert decimals — see how to convert decimals to fractions where GCD simplification appears next.

For any two positive integers a and b:

GCD(a, b) × LCM(a, b) = a × b

(More carefully: GCD(a, b) × LCM(a, b) = |a × b|.)

Check with 48 and 18

• GCD = 6, LCM = 144
• 6 × 144 = 864
• 48 × 18 = 864 ✓

Use it as a shortcut

If you already have GCD(a, b), then LCM(a, b) = |a × b| ÷ GCD(a, b). That is usually faster than listing multiples.

Example: GCD(252, 105) = 21 → LCM = (252 × 105) ÷ 21. First 252 ÷ 21 = 12, then 12 × 105 = 1260.

Multi-number warning

The simple product identity is for two numbers. For three or more, you cannot write GCD(a,b,c) × LCM(a,b,c) = a×b×c in general. Compute multi-number GCD/LCM iteratively: GCD(a, b, c) = GCD(GCD(a, b), c), and likewise for LCM.

Reducing 48:18 with GCD 6 is the same skill as ratio simplification — the free ratio simplifier applies that divisor for you.

Fold the list pairwise (associativity of GCD and LCM).

GCD of a list

GCD(24, 36, 60): GCD(24, 36) = 12; GCD(12, 60) = 12.

LCM of a list

LCM(4, 6, 8): LCM(4, 6) = 12; LCM(12, 8) = 24.

Everyday applications

• Fractions: add 1/8 + 1/12 + 1/18 with LCM of denominators 8, 12, 18 = 72
• Recipes / ratios: divide all parts by GCD so 12:18:30 becomes 2:3:5
• Scheduling: events every 15 and 20 minutes coincide every LCM(15, 20) = 60 minutes
• Tiling / packaging: largest square tile that fits a 48×18 rectangle has side GCD = 6

When fractions become decimals for display, pair this with how to convert fractions to decimals. Part-of-whole percent language still uses separate percent formulas — see the percentage calculator guide.

A good tool shows not only answers but Euclidean steps and factorizations so you can verify homework or code.

1. Open the free GCD and LCM calculator.
2. Enter two or more integers (positive preferred; absolutes handle signs).
3. Read GCD and LCM for the full set.
4. Expand Euclidean algorithm steps for the pairwise GCD chain when shown.
5. Compare prime factorization views: min exponents → GCD, max → LCM.
6. Check GCD × LCM against |a × b| for two-number cases.
7. Use GCD to reduce a fraction or ratio; use LCM for a common denominator.
8. Re-run with a third number to see how the multi-number fold changes results.

Classroom tip: always show at least one Euclidean line or factor list so “calculator said so” is backed by a method you can defend on paper.

Most errors are definition mix-ups, not hard arithmetic.

• Swapping GCD and LCM — GCD ≤ each number; LCM ≥ each number (for positive integers)
• Using min/max of the numbers themselves — GCD(12, 18) is 6, not 12; LCM is 36, not 18
• Stopping Euclidean early — keep going until remainder 0
• Partial common divisors — dividing by 2 when GCD is 6 only partially simplifies
• Applying the product identity to three numbers — it fails in general
• Ignoring units — LCM of 12 inches and 18 inches is fine; mixing inches and feet without converting is not

Quick sanity checks: GCD divides both inputs; both inputs divide LCM; for two positives, product of GCD and LCM equals product of the numbers.

Practice with three pairs from homework or recipes until Euclidean remainder steps feel automatic.