LCM & HCF / GCD Calculator
Find the Least Common Multiple (LCM) and Highest Common Factor (HCF / GCD) for any group of integers.
Smallest positive integer divisible by all numbers
Largest factor that divides all numbers without remainder
Prime Factorization Breakdown
Complete Guide to Least Common Multiple (LCM) & Greatest Common Divisor (GCD / HCF)
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all numbers in a given set, while the Highest Common Factor (HCF / GCD) is the greatest integer that divides each of the numbers without leaving a remainder. These concepts are foundational in simplifying rational polynomials, modular cryptography (RSA), and synchronized interval scheduling.
Prime Factorization Method
Deconstruct every integer into prime exponential factors:
HCF: Product of lowest powers of common prime factors.
LCM: Product of highest powers of all prime factors.
Example (24 & 36): 24 = 2³ × 3¹, 36 = 2² × 3²
• HCF = 2² × 3¹ = 12 | LCM = 2³ × 3² = 72
The Euclidean Algorithm & Relation Formula
The product of two positive integers equals the product of their LCM and GCD:
Fundamental Identity: a × b = LCM(a, b) × HCF(a, b)
Euclidean Division: GCD(a, b) = GCD(b, a mod b)
Fast LCM Formula: LCM(a, b) = |a × b| / GCD(a, b)
Number Pair Prime Factorization, HCF & LCM Benchmarks
| Numbers | Prime Factorization | HCF / GCD | LCM | Product (a × b) Check |
|---|---|---|---|---|
| 12, 18 | 12 = 2²·3, 18 = 2·3² | 6 | 36 | 216 (6 × 36 = 216) |
| 15, 25 | 15 = 3·5, 25 = 5² | 5 | 75 | 375 (5 × 75 = 375) |
| 24, 36, 60 | 24=2³·3, 36=2²·3², 60=2²·3·5 | 12 | 360 | 3-Number Group |
| 17, 19 (Primes) | 17 = 17, 19 = 19 (Coprime) | 1 | 323 | 323 (1 × 323 = 323) |
Frequently Asked Questions (FAQ)
What does it mean if two numbers are "coprime" or relatively prime?
Two numbers are coprime if their only common positive divisor is 1 (HCF = 1). For example, 8 and 9 are both composite numbers, but because GCD(8, 9) = 1, they are coprime, and their LCM is simply their direct product (8 × 9 = 72).
Can the formula LCM(a,b) × HCF(a,b) = a × b be used for three numbers?
No, the identity LCM × HCF = product of numbers holds strictly for two numbers only. For three or more numbers, prime factorization or progressive pairwise reduction must be applied.
How is LCM used in real-world scheduling problems?
LCM solves recurring synchronization problems. If Bus A leaves every 12 minutes and Bus B leaves every 18 minutes, they will depart simultaneously every LCM(12, 18) = 36 minutes.