HCF and LCM by prime factorisation

If you know the prime factorisations of two numbers, finding their HCF (highest common factor, also called GCD) and their LCM (least common multiple) is essentially mechanical. No long division, no guessing , just compare exponents.

Definitions

The HCF (or GCD) of integers $a$ and $b$ is the largest positive integer that divides both. The LCM is the smallest positive integer that is a multiple of both.

If $a = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \qquad b = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k},$ where we have padded with zero exponents so that the same prime list works for both, then $\operatorname{HCF}(a,b) = \prod_{i=1}^{k} p_i^{\min(a_i, b_i)}, \qquad \operatorname{LCM}(a,b) = \prod_{i=1}^{k} p_i^{\max(a_i, b_i)}.$

Theorem and the product rule

Product rule. For any two positive integers $a$ and $b$ , $\operatorname{HCF}(a,b) \cdot \operatorname{LCM}(a,b) = a \cdot b.$

The proof is one line using exponents: for any prime $p$ , $\min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i$ , so the exponent of $p$ on both sides is the same. Multiplying over all primes gives the rule.

Warning. The product rule fails for three or more numbers. For example, $\operatorname{HCF}(2,3,4) = 1$ and $\operatorname{LCM}(2,3,4) = 12$ , but $2 \cdot 3 \cdot 4 = 24$ .

There are several practical consequences. (i) If you know any two of $a$ , $b$ , $\operatorname{HCF}$ , $\operatorname{LCM}$ , you can find the fourth (when you know one of $a$ or $b$ ). (ii) The HCF is always a divisor of the LCM. (iii) If $\operatorname{HCF}(a,b) = 1$ , we say $a$ and $b$ are coprime (or relatively prime); in that case $\operatorname{LCM}(a,b) = ab$ .

The same idea extends to several numbers. For $a, b, c$ , the HCF is the product of $p^{\min}$ over all primes (min taken across all three exponents), and the LCM is the product of $p^{\max}$ . So once the prime factorisations are written down, HCF and LCM are just "stack the columns and take min/max".

This method has a real-world feel. Two traffic lights blink every $48$ and $60$ seconds , when do they blink together again? The LCM of $48$ and $60$ . Three friends jog around a circular track with lap times $24$ , $36$ , and $54$ seconds , when do they next meet at the start? The LCM of $24, 36, 54$ . Cutting wires of length $1.20$ m and $1.80$ m into equal pieces of greatest length? The HCF.

Worked examples

Example 1. Find the HCF and LCM of $96$ and $404$ .

$96 = 2^5 \times 3$ , and $404 = 2^2 \times 101$ . Common primes: only $2$ , with $\min(5,2) = 2$ . $\operatorname{HCF} = 2^2 = 4.$ $\operatorname{LCM} = 2^5 \times 3 \times 101 = 32 \times 303 = 9696.$ Check: $4 \times 9696 = 38784 = 96 \times 404$ . ✓

Example 2. Find the HCF and LCM of $6$ , $72$ , $120$ .

$6 = 2 \times 3$ , $72 = 2^3 \times 3^2$ , $120 = 2^3 \times 3 \times 5$ .

For each prime take min across all three rows for HCF and max for LCM.

Prime $2$ : min $= 1$ , max $= 3$ . Prime $3$ : min $= 1$ , max $= 2$ . Prime $5$ : min $= 0$ , max $= 1$ . $\operatorname{HCF} = 2 \times 3 = 6, \qquad \operatorname{LCM} = 2^3 \times 3^2 \times 5 = 360.$

Example 3. Two numbers are in the ratio $15 : 11$ . If their HCF is $13$ , find the numbers and their LCM.

Two numbers in ratio $15:11$ can be written as $15k$ and $11k$ . Since $\operatorname{HCF}(15,11) = 1$ , the HCF of $15k$ and $11k$ is $k$ . So $k = 13$ , giving numbers $15 \times 13 = 195$ and $11 \times 13 = 143$ . Then $\operatorname{LCM} = \frac{195 \times 143}{13} = 15 \times 143 = 2145.$

Example 4. Three bells ring at intervals of $9$ , $12$ , and $15$ minutes. They all rang together at $8:00$ a.m. When will they next ring together?

LCM $(9,12,15)$ . $9 = 3^2$ , $12 = 2^2 \times 3$ , $15 = 3 \times 5$ . LCM $= 2^2 \times 3^2 \times 5 = 180$ minutes $= 3$ hours.

They ring together again at $11:00$ a.m.

Example 5. Can the HCF of two numbers be $18$ and their LCM be $380$ ?

If yes, then HCF should divide LCM: $18 \mid 380$ ? $380 / 18 = 21.11\ldots$ , not an integer. Contradiction. So no, such numbers do not exist.

Try it yourself

Find the HCF and LCM of $26$ and $91$ .
Find the HCF and LCM of $510$ and $92$ .
Find the HCF and LCM of $336$ and $54$ , and verify the product rule.
Find the LCM of $12$ , $15$ , $21$ .
Find the HCF of $40$ , $60$ , $75$ .
The HCF of two numbers is $9$ and their LCM is $90$ . If one number is $18$ , find the other.
Two tankers, of capacities $850$ and $680$ litres, are filled with the same kind of oil from a common container. Find the maximum capacity of a vessel that can measure the oil in either tanker an exact number of times.
Three runners complete a lap in $48$ , $60$ , and $72$ seconds. When do they next meet at the starting point?
If $\operatorname{HCF}(a,b) = 1$ and $a \cdot b = 540$ , list all possible pairs $(a,b)$ .
Show that for any $a, b$ , $\operatorname{LCM}(a,b)$ is a multiple of $\operatorname{HCF}(a,b)$ .

Pitfalls / Insight

Product rule for three or more numbers is wrong. Use prime factorisation directly.
Don't forget to write $0$ exponents for primes that appear in one number but not the other. They still count when comparing.
HCF divides LCM, and both divide the LCM , useful sanity check.

Insight. The "min and max" picture turns HCF/LCM questions into bookkeeping with exponents. Once you write the prime factorisations as columns, you can almost see the answer.