HCF from prime factorisation

Now put the two ideas together. Every factor is a subpart of a prime factorisation, so every COMMON factor is a subpart of BOTH factorisations.

Find the common factors and HCF of 45 and 75. Their factorisations are 45 = 3 × 3 × 5 and 75 = 3 × 5 × 5. Which subparts appear in both? A single 3, a single 5, and 3 × 5 = 15. Together with 1, those are the common factors, and the highest is 15. So the HCF is 15.

Another: 112 = 2 × 2 × 2 × 2 × 7 and 84 = 2 × 2 × 3 × 7. Common subparts are 2, 7, 2 × 2, 2 × 7 and 2 × 2 × 7. The highest is 2 × 2 × 7 = 28, so the HCF is 28.

And a case with nothing shared: 96 = 2 × 2 × 2 × 2 × 2 × 3 and 275 = 5 × 5 × 11. No prime appears in both, so there is no common subpart at all. The only common factor is 1, and 1 is their HCF.

Listing every common subpart still takes time. Can we get the HCF directly? Yes — build the largest common subpart straight away.

Take 30 = 2 × 3 × 5 and 72 = 2 × 2 × 2 × 3 × 3. The largest common subpart can only contain primes appearing in BOTH: here 2 and 3. How many 2s? 30 has only one, so the common subpart can have only one. How many 3s? 30 has only one, so again only one. So HCF = 2 × 3 = 6.

The rule: identify the COMMON primes, and take each the MINIMUM number of times it appears across the factorisations. Try it on 225 = 3 × 3 × 5 × 5 and 750 = 2 × 3 × 5 × 5 × 5. Common primes 3 and 5. The minimum count of 3 is one (750 has one); the minimum count of 5 is two (225 has two). So HCF = 3 × 5 × 5 = 75. The same method extends to more than two numbers.