LCM and HCF
Finding the largest shared factor and the smallest shared multiple of two or more numbers, and using them to solve real grouping and timing problems.
What you'll learn
- Find the HCF of two numbers using prime factorization or the Euclidean algorithm
- Find the LCM of two or more numbers and verify it using LCM x HCF = product of the two numbers
- Apply LCM to word problems about events recurring together and HCF to word problems about splitting quantities evenly
Prerequisites
Explanation
The HCF (Highest Common Factor, also called GCD) of two numbers is the largest number that divides both of them with no remainder. The LCM (Least Common Multiple) is the smallest number that both of them divide into evenly. They answer opposite questions: HCF asks "what's the biggest thing I can split both quantities into evenly?" and LCM asks "what's the smallest quantity both of these fit into evenly?"
Prime factorization method. Break each number into prime factors, then:
- HCF = product of the lowest power of every prime that appears in both factorizations.
- LCM = product of the highest power of every prime that appears in either factorization.
Worked example. Take 18 and 24. 18 = 2¹ × 3², and 24 = 2³ × 3¹. For HCF, take the lower power of each shared prime: 2¹ × 3¹ = 6. For LCM, take the higher power of each prime that appears anywhere: 2³ × 3² = 8 × 9 = 72. A useful check exists precisely because of this structure: for any two numbers, LCM × HCF = the product of the two numbers. Here, 6 × 72 = 432, and 18 × 24 = 432 — they match, confirming the arithmetic. (This shortcut only holds for exactly two numbers, not three or more.)
For larger or less obviously-factored numbers, the Euclidean algorithm finds HCF without factoring anything: repeatedly replace the larger number with the remainder of dividing it by the smaller one, until the remainder is 0 — whatever's left is the HCF. For 18 and 24: 24 ÷ 18 leaves remainder 6; 18 ÷ 6 leaves remainder 0; so HCF = 6, matching the factorization method. Once you have HCF this way, LCM = (a × b) ÷ HCF.
Word problems tend to fall into two shapes:
- "When do they align again?" → LCM. Three temple bells ring every 12, 18, and 30 minutes respectively, all starting together. They'll next ring together after LCM(12, 18, 30) minutes — the smallest time that's a multiple of all three intervals.
- "What's the biggest even split?" → HCF. You have 48 pencils and 60 notebooks and want to pack them into identical gift bags with no items left over, using the fewest bags possible (so, the largest possible bag size). The largest number of sets you can make is HCF(48, 60) = 12, meaning each bag gets 4 pencils and 5 notebooks.
The pattern to remember: LCM problems involve things happening repeatedly and asking when they coincide; HCF problems involve splitting things into identical groups with nothing left over.
Example
The Euclidean algorithm finds HCF quickly; LCM follows from LCM x HCF = product of the two numbers.
function hcf(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function lcm(a, b) {
if (a === 0 || b === 0) return 0;
return Math.abs(a * b) / hcf(a, b);
}
// Example: hcf(18, 24) -> 6, and lcm(18, 24) -> 72.Guided exercise
Guided exercise
Write hcf(a, b) that returns the highest common factor of two non-negative integers a and b using the Euclidean algorithm (repeated remainder division). hcf(0, n) should return n, matching the standard convention.
Checks: Finds the HCF of two composite numbers · Finds the HCF of two coprime numbers is 1 · plus 1 hidden check
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write ringTogetherAfter(intervals) modeling several bells that all ring together at time 0, where intervals is an array of positive integers giving each bell's ringing interval in minutes. Return the number of minutes until all the bells ring together again -- the LCM of every number in the array.
Checks: Finds the LCM of three intervals · Finds the LCM of two intervals · plus 1 hidden check
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Applying LCM x HCF = product of the numbers to three or more numbers at once — that identity only holds for exactly two numbers.
- Mixing up which problem type needs LCM versus HCF — 'when do repeating events coincide' needs LCM, 'largest even split with nothing left over' needs HCF.
- Forgetting to take the lowest shared power of each prime for HCF (using the highest power instead, which is how LCM is computed).
Knowledge check
Takeaway
HCF finds the biggest thing two quantities share; LCM finds the smallest thing they both fit into -- and for exactly two numbers, their product ties both together.
Summary
Prime factorization gives HCF from the lowest shared prime powers and LCM from the highest prime powers present anywhere, while the Euclidean algorithm finds HCF directly by repeated remainder division. LCM answers 'when do repeating events coincide,' and HCF answers 'what's the largest even split with nothing left over.'
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.