GCD & LCM Guide: Meaning, Formulas, Steps + Mini Calculator

Understand GCD (HCF) and LCM with Euclidean algorithm steps, prime factors, and practical examples — plus an interactive mini calculator.

Examples-firstStep-by-stepInteractive9 min read• Updated Jan 15, 2026

What is GCD (HCF)?

GCD (or HCF) is the largest integer that divides two (or more) integers exactly.

GCD stands for Greatest Common Divisor. In many school contexts it is called HCF (Highest Common Factor). Both mean the same thing.

You can think of the GCD as the “largest shared chunk size” that fits into both numbers with no remainder. It is used for simplifying fractions, reducing ratios, and grouping items evenly.

Example
  • GCD(12, 18) = 6
  • Because 6 divides 12 and 18 exactly.
Open full GCD & LCM Calculator →
GCD never increases when adding more numbers
For multiple numbers, the GCD can only stay the same or get smaller as you include more values.
Key takeaway
GCD/HCF is the biggest number that divides all inputs exactly.

What is LCM?

LCM is the smallest positive integer that is a multiple of each input number.

LCM stands for Least Common Multiple. It is the first point where multiple repeating cycles “line up” again.

LCM is used for adding fractions (common denominator), scheduling problems (events repeating every N days), and synchronizing repeating patterns.

Example
  • LCM(4, 6) = 12
  • Because 12 is the smallest number divisible by both 4 and 6.
Open full GCD & LCM Calculator →
LCM can get large fast
Even for medium-sized inputs, the LCM can grow beyond safe integer ranges. Our full calculator handles large results and shows exact values when needed.
Key takeaway
LCM is the smallest shared multiple — where cycles align.

GCD vs LCM (Differences)

GCD helps with simplification; LCM helps with alignment.

GCD answers: “What is the biggest shared factor?” LCM answers: “What is the smallest shared multiple?”

They are complementary. For two numbers a and b (not both zero), there is a useful relationship between them: GCD(a,b) × LCM(a,b) = |a×b|.

Example
  • For 12 and 18:
  • GCD = 6
  • LCM = 36
  • 6 × 36 = 216 = |12 × 18|
Quick comparison
FeatureGCD (HCF)LCM
MeaningGreatest common divisorLeast common multiple
Typical useSimplify fractions/ratiosCommon denominators/schedules
SizeUsually smallerUsually larger
Key takeaway
Use GCD to simplify, use LCM to align.

Euclidean Algorithm (Steps)

The fastest way to compute GCD uses repeated division with remainder.

Euclidean algorithm repeatedly applies: a = q×b + r. Replace (a, b) with (b, r) until the remainder is 0. The last non-zero remainder is the GCD.

This method is efficient and works well even for large integers compared to listing factors.

Euclidean steps for (252, 105)
  • 252 = 2×105 + 42
  • 105 = 2×42 + 21
  • 42 = 2×21 + 0
  • GCD = 21
Open full GCD & LCM Calculator →
LCM via GCD
Once you know GCD(a,b), you can compute LCM(a,b) = |a/GCD(a,b)| × |b| (and extend to more numbers by chaining).
Key takeaway
Euclidean algorithm gives GCD quickly using remainders.

Prime Factorization Method

GCD uses the minimum shared prime powers; LCM uses the maximum prime powers.

Write each number as a product of primes. The GCD is formed by taking primes common to all numbers with the smallest exponent. The LCM is formed by taking primes appearing in any number with the largest exponent.

This method is excellent for understanding, but for big numbers it can be slow compared to Euclid.

Prime factors example
  • 12 = 2^2 × 3
  • 18 = 2 × 3^2
  • GCD = 2^1 × 3^1 = 6
  • LCM = 2^2 × 3^2 = 36
Open full GCD & LCM Calculator →
Key takeaway
Prime factors: min exponents → GCD, max exponents → LCM.

Relationship: GCD × LCM

For two numbers a and b, GCD(a,b) × LCM(a,b) = |a×b| (unless both are 0).

This identity is a great sanity check and helps derive LCM from GCD. It holds for integers with the common convention GCD(0,0)=0 and LCM(0,0)=0.

If either number is 0, the LCM is 0 (because every multiple of 0 is 0), and the GCD is the absolute value of the other number.

Example
  • a=0, b=15
  • GCD(0,15)=15
  • LCM(0,15)=0
Open full GCD & LCM Calculator →
Coprime shortcut
If GCD(a,b)=1, the numbers are coprime and LCM(a,b)=|a×b|.
Key takeaway
For two numbers: GCD×LCM equals the absolute product.

GCD/LCM of Multiple Numbers

Compute across many numbers by chaining pairwise results: GCD(GCD(a,b),c)... and similarly for LCM.

Most calculators (including ours) compute the result across multiple numbers by reducing the list step by step. This is reliable and easy to explain.

Important: if all inputs are 0, both GCD and LCM are defined as 0. If some are 0, the GCD ignores zeros naturally, while LCM becomes 0 if any input is 0.

Example
  • GCD(24, 36, 60) = 12
  • LCM(3, 4, 6) = 12
The full calculator supports 2–10 integers, optional step chains, and prime factor visuals.
Open full GCD & LCM Calculator →
Key takeaway
For many numbers, reduce step-by-step; watch out for zeros.

Real-World Use Cases

GCD simplifies; LCM synchronizes.

GCD: simplifying fractions (12/18 → 2/3), reducing ratios (20:30 → 2:3), dividing items into equal groups.

LCM: scheduling (events every 6 and 8 days align every 24 days), adding fractions (common denominator), repeating patterns.

Scheduling example
  • Bus A every 6 days, Bus B every 8 days
  • They align every LCM(6,8)=24 days
Key takeaway
Use GCD for “largest shared divisor”, LCM for “smallest shared multiple”.

Quick Reference

Keep these formulas handy for exams and quick checks.

GCD and LCM are easiest when you remember a few safe formulas and special cases.

For two integers a and b (not both zero): LCM(a,b) = |a/GCD(a,b)| × |b|. If either input is 0, LCM is 0.

Quick rules
  • GCD(a,0)=|a|
  • LCM(a,0)=0
  • If GCD(a,b)=1 ⇒ LCM(a,b)=|a×b|
ScenarioGCDLCM
a and b are coprime1|a×b|
a = b|a||a|
one input is 0|other|0
Key takeaway
Remember the identity and the zero cases.

FAQs

Is GCD the same as HCF?
Yes. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are the same concept with different names.
What is GCD(0, 0)?
By common convention used in programming and math utilities, GCD(0,0) is defined as 0.
What is LCM(a, 0)?
LCM(a,0) is 0 for any integer a, because the only multiple of 0 is 0.
How do you find LCM using GCD?
For two integers a and b (not both zero): LCM(a,b) = |a/GCD(a,b)| × |b|. This avoids prime factorization.
Can LCM be smaller than both numbers?
No. For positive integers, the LCM is always at least as large as the larger input, unless one input is 0 (then LCM is 0).
Related
Open the full GCD & LCM CalculatorFraction GuidePercentage Guide
Back to Calculator ↑

Want step-by-step for multiple numbers?

Open the full calculator to compute GCD/LCM for 2–10 integers, with optional Euclidean chains and prime factor visuals.

Open GCD & LCM Calculator