RadfordMathematics.com

Online Mathematics Book

HCF & LCM using Prime Factorization


We use prime factorization, that's writing a number as a product of its prime factors, to find two (or more) numbers' Highest Common Factor (HCF) and Least Common Multiple (LCM).
This is very useful when trying to find the HCF, or LCM, of large numbers.

Highest Common Factor (HCF)


  • Step 1: write both whole numbers as products of their prime factors.
    For \(36\) and \(120\) that would be: \[36 = 2^2 \times 3^2\]
    and
    \[120 = 2^3 \times 3 \times 5\]
  • Step 2: The HCF equals to the product of the prime factors both numbers have in common, each of which is raised to the lowest power seen.
    For \(36\) and \(120\), the prime factors they have in common are: \[2 \quad \text{and} \quad 3\] The lowest power of \(2\) is \(2^2\), the lowest power of \(3\) is \(3\). So the highest common factor, HCF, is: \[HCF(36,120) = 2^2\times 3\]

Least Common Multiple (LCM)


  • Step 1: write both whole numbers as products of their prime factors.
    For \(36\) and \(120\) that would be: \[36 = 2^2 \times 3^2\]
    and
    \[120 = 2^3 \times 3 \times 5\]

  • Step 2: The LCM equals to the product of all the distinct prime factors seen, each of which is raised to the highest power seen.
    For \(36\) and \(120\), the prime factors seen are: \[2, \ 3, \ 5\] The highest power of \(2\) is \(2^3\), the highest power of \(3\) is \(3^2\) and the highest power of \(5\) is \(5\). So the least common multiple, LCM, is: \[LCM(36,120) = 2^3\times 3^2\times 5\]

Tutorial

In the following tutorial we review the method for finding two numbers' least common multiple using prime factorization.

Exercise


Leaving your answers as products of prime factors, find the Highest Common Factor, HCF, and the Least Common Multiple, LCM, of each of the following pairs of whole numbers:

  1. \(75\) and \(20\)

  2. \(90\) and \(84\)

  3. \(36\) and \(60\)

  4. \(225\) and \(135\)

Answers Without Working

  1. \(HCF = 5\) and \(LCM = 2^2\times 3 \times 5^2\)

  2. \(HCF(90,84) = 2\times 3\) and \(LCM(90,84) = 2^2 \times 3^2 \times 5 \times 7\)

  3. \(HCF(36,60) = 2^2 \times 3\) and \(LCM(36,60) = 2^2 \times 3^2 \times 5\).

  4. \(HCF(225,135) = 3^2 \times 5\) and \(LCM(225,135) = 3^3 \times 5^2\)