LCM and HCF — Why These Two Numbers Unlock Most of Arithmetic
The Least Common Multiple (LCM) and Highest Common Factor (HCF) — also called LCM and GCD (Greatest Common Divisor) in different curricula — are two of the most practically useful concepts in number theory. They appear in everything from adding fractions to writing software that synchronises repeating events, from scheduling maintenance intervals to cutting fabric into equal pieces without waste.
At their core, the relationship is elegantly simple: LCM(a, b) × HCF(a, b) = a × b for any two positive integers. This means if you know one, you can always find the other. But the applications of each are quite different — HCF is for dividing and simplifying; LCM is for combining and synchronising.
When to Use LCM vs When to Use HCF
Use HCF when you need to divide into equal groups. Distributing 24 apples and 36 oranges into identical bags (maximum bags, no leftovers): HCF(24, 36) = 12 bags, each with 2 apples and 3 oranges. Simplifying the fraction 36/48: HCF(36, 48) = 12, so 36/48 = 3/4. Finding the largest square tiles that fit exactly in a 360 cm × 540 cm floor without cutting: HCF(360, 540) = 180 cm tiles.
Use LCM when you need the earliest moment of synchronisation. Two buses leaving a terminus every 12 and 18 minutes respectively: next simultaneous departure in LCM(12, 18) = 36 minutes. Adding fractions: 1/6 + 1/4 requires the common denominator LCM(6, 4) = 12, giving 2/12 + 3/12 = 5/12. Events that repeat every 3 and 5 years coinciding: in LCM(3, 5) = 15 years. Also see our Fraction Calculator and GST Calculator.
The Three Methods This Calculator Uses
Prime Factorisation — factor each number into primes, then HCF takes minimum powers and LCM takes maximum powers. Best for understanding the structure, not for large numbers. Division Method — repeatedly divide all numbers by their common prime factors. Compact and easy to show in a table. Euclidean Algorithm — uses the identity GCD(a, b) = GCD(b, a mod b) repeatedly until the remainder is 0. The fastest method computationally and works for large numbers without needing prime factors.
LCM & HCF Calculator
Enter 2 to 6 numbers — get LCM, HCF, prime factorisations and step-by-step working in 3 methods
Solution Summary
All 3 Methods — Comparison
Prime Factor Breakdown
Division Method Table
Step-by-Step Working
What Are LCM and HCF?
Definitions, relationship, key properties and why these concepts appear everywhere in maths and daily life
The Highest Common Factor (HCF) — also called Greatest Common Divisor (GCD) or Greatest Common Factor (GCF) — is the largest positive integer that divides each of the given numbers without leaving a remainder. The HCF of 12 and 18 is 6 because 6 is the largest number that divides both exactly.
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all of the given numbers. The LCM of 12 and 18 is 36 because 36 is the smallest number that both 12 and 18 divide into exactly. Every common multiple of the numbers is a multiple of the LCM.
HCF and LCM are used in simplifying fractions (HCF to reduce, LCM to add/subtract), scheduling problems (when will two periodic events align?), gear ratios, tiling problems, music rhythm theory, and computer science (hash tables, memory alignment, and cyclic redundancy checks). They are among the oldest and most practically useful ideas in mathematics.
Three Methods — When to Use Each
Prime Factorisation, Division Method and Euclidean Algorithm compared with examples and use cases
| Method | Approach | Best When | Limitation |
|---|---|---|---|
| Prime Factorisation Most educational | Express each number as product of primes; HCF = min powers, LCM = max powers | Numbers up to ~200; teaching/learning; 3+ numbers | Slow for large numbers; finding prime factors can be tedious |
| Division Method (Ladder) | Divide all numbers by common prime factors; HCF = product of divisors, LCM = product of all primes used | Finding LCM of 3+ numbers; exam problems | Slightly mechanical; easy to miss a prime factor |
| Euclidean Algorithm Fastest for 2 numbers | GCD(a,b) = GCD(b, a mod b) until remainder = 0; then LCM = a×b / HCF | Large numbers; two numbers; programming | Only directly gives HCF of two numbers at a time |
| Listing Multiples/Factors | List multiples of each number; LCM = first common multiple. List factors; HCF = largest common | Small numbers; mental maths; beginners | Impractical for large numbers |
Prime Factorisation Worked
12 = 2² × 3, 18 = 2 × 3². Common primes: 2 (min power 1) and 3 (min power 1). HCF = 2¹ × 3¹ = 6. All primes: 2 (max power 2) and 3 (max power 2). LCM = 2² × 3² = 36. Check: 6 × 36 = 216 = 12 × 18. ✓
Step by stepDivision Method Worked
Write 12 and 18 in a row. Divide by smallest prime that divides at least one: 2→6,9; 2→3,9; 3→1,3; 3→1,1. HCF = product of primes that divided ALL numbers = 2×3 = 6. LCM = product of ALL primes used = 2×2×3×3 = 36.
Ladder methodEuclidean Algorithm Worked
GCD(18,12): 18 = 1×12 + 6; GCD(12,6): 12 = 2×6 + 0; remainder = 0, so GCD = 6 = HCF. LCM = 18×12 / 6 = 216 / 6 = 36. The algorithm is guaranteed to terminate and is extremely fast even for numbers with hundreds of digits.
FastestLCM for Adding Fractions
To add 5/12 + 7/18, find LCM(12,18) = 36. Convert: 5/12 = 15/36, 7/18 = 14/36. Sum = 29/36. The LCM becomes the lowest common denominator (LCD). Without LCM, you'd use 12×18=216 as denominator and get larger numbers to simplify later.
FractionsLCM for Scheduling
Bus A comes every 12 minutes, Bus B every 18 minutes. Both just left at 9:00 AM. When do they next leave together? LCM(12,18) = 36 minutes later → 9:36 AM. Any problem of the form "after how long do two periodic events coincide?" is an LCM problem.
Real worldHCF for Tiling Problems
A room is 360 cm × 252 cm. What is the largest square tile that fits exactly? HCF(360, 252). 360 = 2³×3²×5, 252 = 2²×3²×7. HCF = 2²×3² = 36 cm. So 36×36 cm tiles work perfectly with no cutting. HCF gives the largest unit that fits both dimensions exactly.
Classic useHow This Calculator Works
Step-by-step: how inputs are processed, prime factorisations found, and all three methods applied
- 1
Enter 2 to 6 Positive Integers
Fill the input boxes with any positive integers from 1 to 999,999. Optional boxes (marked "opt") are skipped automatically. The preset buttons and quick chips instantly load common example sets so you can explore without typing.
- 2
Prime Factorisation of Each Number
The calculator trial-divides each number by 2, 3, 5, 7, 11 … up to its square root to find all prime factors and their powers. Results are displayed as colour-coded factor badges — common factors highlighted in green, unique factors in blue.
- 3
HCF = Min Powers, LCM = Max Powers
Across all prime factorisations: HCF takes each prime factor at its minimum exponent across all numbers. LCM takes each prime factor at its maximum exponent. For 3+ numbers, this is extended naturally — the logic is identical.
- 4
All 3 Methods Computed — Selected Method Shown in Full
Prime Factorisation, Division Method table, and Euclidean Algorithm steps are all computed. The selected method toggle controls which one gets the full step-by-step working in the steps list. The Method Comparison section always shows all three results side by side.
- 5
Verification — Golden Relationship Check
For two numbers, the calculator always verifies LCM × HCF = a × b and displays whether the check passes. Visual proportion bars show each number's prime factorisation as a proportion of the LCM, making it easy to see which factors each number contributes.
HCF(a,b) = product of common prime factors (min powers)
LCM(a,b) = product of all prime factors (max powers)
HCF × LCM = a × b (for two numbers only)
LCM(a,b,c) = LCM(LCM(a,b), c)
HCF(a,b,c) = HCF(HCF(a,b), c)
Euclidean : GCD(a,b) = GCD(b, a mod b) until b=0LCM & HCF Facts, Tricks & Real-World Uses
Fascinating properties, shortcuts, history and applications you were never taught in school
Euclid's Algorithm Is 2,300 Years Old
The Euclidean Algorithm for finding GCD appears in Euclid's Elements (c. 300 BC), making it one of the oldest algorithms still in common use. It is more efficient than prime factorisation for large numbers — finding GCD(1,000,000,007 and 998,244,353) takes only a few steps by repeated division, while factorising those numbers would take far longer.
LCM Powers All Fraction Arithmetic
Whenever you add or subtract fractions with different denominators in school, you are finding an LCM — specifically the Lowest Common Denominator (LCD), which is exactly LCM(denominators). Without the LCM, fraction addition requires multiplying denominators together and then simplifying — the LCM shortcut avoids that extra simplification step.
RSA Encryption Uses Co-prime Numbers
The RSA cryptographic algorithm — used in HTTPS, banking, and secure email — relies on choosing two large co-prime numbers. The security comes from the fact that while HCF(e, φ(n)) = 1 is easy to verify, recovering the factors of n from e and the public key is computationally infeasible. Every secure website you visit uses this principle.
Gear Ratios and LCM
In mechanical engineering, two meshing gears with tooth counts a and b will repeat the same pair of teeth engaging after LCM(a,b) rotations total. Engineers choose gear tooth counts to avoid repeated wear on the same teeth — which means deliberately choosing numbers with a high LCM (i.e. low HCF, ideally co-prime). This extends gear life significantly.
HCF Simplifies Ratios in Finance
Sharing profits in a ratio of 48:36:24 — find HCF(48,36,24) = 12, so the simplified ratio is 4:3:2. Interest calculations, mixture problems and investment allocations all reduce to finding HCF to simplify the underlying ratio. The "simplest form" of any ratio is found by dividing all terms by their HCF.
Music Theory and LCM
In music, polyrhythms occur when two rhythms with different beat counts play simultaneously. A 3-against-4 polyrhythm (triplet vs. quarter notes) repeats every LCM(3,4) = 12 subdivisions. West African drumming, jazz, and contemporary classical music all use polyrhythms whose period is an LCM. Every musician who plays in compound time is implicitly using LCM.
Computer Science: Memory Alignment
CPUs access memory most efficiently when data is aligned to multiples of its size. When you need a buffer that's accessible for two data structures of sizes a and b bytes, the alignment requirement is LCM(a,b). Compiler padding, struct layout, SIMD instruction alignment requirements — all solved with LCM arithmetic under the hood.
The LCM of 1 to n Grows Exponentially
LCM(1,2,3,...,n) grows roughly as e^n by the prime number theorem. LCM(1..10) = 2520. LCM(1..20) = 232,792,560. LCM(1..30) ≈ 2.3 × 10¹⁴. This exponential growth is related to why the harmonic series diverges and appears in estimates for the distribution of prime numbers — a deep connection between LCM and prime counting.
Frequently Asked Questions
Common questions about LCM, HCF, co-prime numbers, the Euclidean Algorithm and practical uses
Fabric & Tile Cutting
Cutting 360 cm and 540 cm lengths into equal pieces without wastage: HCF(360, 540) = 180 cm. Each piece is exactly 180 cm and both lengths divide evenly. HCF finds the largest unit that divides all given lengths without remainder.
HCF(360,540) = 180Bus & Train Scheduling
Bus A departs every 12 minutes, Bus B every 18 minutes. Next time they leave together: LCM(12, 18) = 36 minutes. This synchronisation problem appears in transport planning, manufacturing cycle timing, and software task scheduling.
LCM(12,18) = 36 minFraction Arithmetic
To add 1/6 + 1/4, find LCM(6,4) = 12. Convert: 2/12 + 3/12 = 5/12. LCM gives the smallest common denominator, keeping numbers manageable. Without LCM, you multiply denominators (24) and get 4/24 + 6/24 = 10/24 = 5/12 — same answer, bigger numbers.
LCM(6,4)=12 → 5/12Equal Distribution
Distributing 24 pens and 36 notebooks into identical sets (no remainders, maximum sets): HCF(24,36) = 12 sets. Each set has 2 pens and 3 notebooks. HCF solves any "divide into equal groups without remainder" problem.
HCF(24,36) = 12 setsSoftware & Cryptography
The Euclidean Algorithm (which this calculator uses) is the foundation of RSA encryption — the most widely used public-key cryptosystem. Extended Euclidean Algorithm finds modular inverses used in digital signatures. LCM is used for synchronising timer interrupts in operating systems.
RSA uses Euclidean AlgoFloor & Wall Tiling
Finding the largest square tile that fits a 4.8 m × 3.6 m room exactly: HCF(480, 360) = 120 cm tiles. Finding when two periodic maintenance cycles (every 8 and 12 weeks) coincide next: LCM(8, 12) = 24 weeks. Both problems solved with one calculator.
HCF(480,360)=120 cm