1.4 - Prime factorisation, HCF and LCM

Prime factors reveal how whole numbers are built. You will express integers as products of prime powers, then use those powers to find the highest common factor and lowest common multiple. You will also decide which quantity answers a grouping or repeating-events problem.

Products of prime powers

You have $84$ red beads and $126$ blue beads. How many identical packs can you make if you use every bead and want as many packs as possible? Listing factors would work, but prime powers give us a more organised route.

You already know

A factor divides a number exactly. A prime number is a positive integer with exactly two positive factors, itself and $1$ . Index notation records repeated factors: $2^3=2\times2\times2$ .

Break a composite number into smaller factors. Keep splitting until every end value is prime, then multiply all those end values. Different first splits give the same prime factors, possibly in a different order.

Prime factorisation

A prime factorisation writes an integer greater than $1$ as a product of prime numbers. A product of prime powers groups equal prime factors using indices. For example, $12=2^2\times3$ . The expression $2\times6$ equals $12$ , but is not a prime factorisation because $6$ is composite. The number $1$ is not prime and has no prime factors.

In this tree, the coloured end values are prime. The uncoloured intermediate values must be split further. Count every end value once, including repeated primes.

[DIAGRAM: asset_name: Prime factor tree for 360; asset_slug: m008-prime-factor-tree; caption: A factor tree splits 360 until every end value is prime.; description: Exact factor tree: 360 splits into 36 and 10, 36 into two sixes, each six into 2 and 3, and 10 into 2 and 5. The six prime leaves give 2 cubed times 3 squared times 5.]

Repeated division is an equally valid method. Divide by a prime factor, then divide the quotient again until it becomes $1$ . Neither method is supplied on the Foundation or Higher formulae sheet: learn it.

Worked example 1: collect repeated prime factors

Question. Express $360$ as a product of powers of prime factors.

Plan. Divide repeatedly by small primes, then count each prime's occurrences.

\begin{aligned} 360&=2\times180=2^2\times90 &&\text{extract two factors of }2\\ &=2^3\times45 &&\text{extract one more }2\\ &=2^3\times3\times15 &&\text{extract a factor of }3\\ &=2^3\times3^2\times5 &&\text{all remaining factors are prime} \end{aligned}

Why stop at $5$ ? It is prime, so it cannot be split into smaller factors greater than $1$ .

Answer. $360=2^3\times3^2\times5$ .

Check. $8\times9\times5=360$ ; the tree gives the same six prime factors.

Now double the integer. Only one extra factor of $2$ is needed, so its index increases by one.

Worked example 2: double the integer

Question. Express $720$ as a product of powers of prime factors.

Plan. Use the factorisation of $360$ and include the additional factor $2$ .

\begin{aligned} 720&=2\times360 &&\text{twice the previous integer}\\ &=2\times2^3\times3^2\times5 &&\text{replace }360\text{ by its factors}\\ &=2^4\times3^2\times5 &&\text{collect the four factors of }2 \end{aligned}

Why does only one index change? Multiplying by $2$ adds a factor of $2$ , without adding a $3$ or a $5$ .

Answer. $720=2^4\times3^2\times5$ .

Check. $16\times9\times5=720$ .

A prime that occurs once may be written without the index $1$ . Factor order does not change a product, but the number of copies matters.

Watch out

Wrong: $360=2^3\times3\times15$ as a finished prime factorisation. Although the value is correct, $15$ is not prime. Split $15=3\times5$ to reach $2^3\times3^2\times5$ .

If “powers of prime factors” are requested, collect repeated primes in the final line. This also makes HCF and LCM easier to read next.

Highest common factor and equal groups

A number of identical packs must divide both bead totals exactly. To make the greatest possible number of packs, choose the greatest factor shared by the totals.

Highest common factor

The highest common factor, or HCF, is the greatest positive integer that divides every given number exactly. For example, $6$ is the HCF of $12$ and $18$ ; $3$ is common too, but is not the highest.

In prime powers, keep only primes present in every number, using the smallest index for each. A common factor cannot take more copies of a prime than the number with the fewest copies supplies. Keeping all those shared copies makes the factor as large as possible. This method is absent from both tier formulae sheets: learn it.

Worked example 3: make the greatest number of packs

Question. Put $84$ red beads and $126$ blue beads into identical packs, using every bead. Find the greatest possible number of packs and the contents of each.

Plan. Find the HCF for the pack count, then divide each bead total by it.

\begin{aligned} 84&=2^2\times3\times7 &&\text{factorise the first total}\\ 126&=2\times3^2\times7 &&\text{factorise the second total}\\ \operatorname{HCF}(84,126)&=2\times3\times7=42 &&\text{use shared minimum powers}\\ 84\div42&=2,\qquad126\div42=3 &&\text{find the contents of one pack} \end{aligned}

Why use the smaller index of each shared prime? Every pack count must divide both totals, so it cannot demand a prime factor that either total lacks.

Answer. $42$ packs, each containing $2$ red beads and $3$ blue beads.

Check. $42\times2=84$ and $42\times3=126$ ; every bead is used.

Now change only the number of blue beads. The shared prime factors may stay the same even though the pack contents change.

Worked example 4: change one total

Question. Put $84$ red beads and $210$ blue beads into identical packs, using every bead. Find the greatest possible number of packs and the contents of each.

Plan. Recalculate the shared minimum powers, then divide to find the contents.

\begin{aligned} 84&=2^2\times3\times7 &&\text{first total is unchanged}\\ 210&=2\times3\times5\times7 &&\text{factorise the new total}\\ \operatorname{HCF}(84,210)&=2\times3\times7=42 &&\text{the factor }5\text{ is not shared}\\ 84\div42&=2,\qquad210\div42=5 &&\text{contents of one pack} \end{aligned}

Why leave out $5$ ? A pack count containing it would not divide $84$ .

Answer. $42$ packs, each containing $2$ red beads and $5$ blue beads.

Check. $42\times2=84$ and $42\times5=210$ , with no remainder.

HCF also gives the longest equal piece length when you cut two lengths into whole pieces with nothing left. Read what the answer represents: a number of groups and the contents of one group are different quantities.

Watch out

Wrong: the HCF of $84$ and $210$ includes $5$ because it appears in one factorisation. An HCF uses shared primes only. Here it is $2\times3\times7=42$ , not $210$ .

For three or more totals, a prime must be present in every total. If no prime is shared by all of them, the HCF is $1$ .

Lowest common multiple and repeating events

A shared repeating interval must contain a whole number of each event's periods. That makes it a multiple of each period, rather than a factor of them.

Lowest common multiple

The lowest common multiple, or LCM, is the smallest positive integer that is a multiple of every given number. For example, the LCM of $4$ and $6$ is $12$ . Although $24$ is also a common multiple, it is not the lowest. Zero is excluded.

Use every prime that occurs in any factorisation, with the largest index needed. This supplies enough copies for each original integer to divide the result. Any smaller selection would leave at least one integer unable to divide it. This method is not in either tier's formulae sheet: learn it.

Worked example 5: find the next shared event

Question. Two bells ring every $18$ minutes and every $24$ minutes. They both ring at $10{:}00$ . At what time do they next ring together?

Plan. Find the LCM of the periods, then add that interval to the starting time.

\begin{aligned} 18&=2\times3^2,\qquad24=2^3\times3 &&\text{factorise both periods}\\ \operatorname{LCM}(18,24)&=2^3\times3^2=72 &&\text{take the largest needed powers}\\ 72\,\mathrm{min}&=1\,\mathrm{h}\ 12\,\mathrm{min} &&\text{convert using sixty minutes per hour} \end{aligned}

Why use the LCM? The next shared interval must be a multiple of both periods, and we want the smallest positive one.

Answer. They next ring together at $11{:}12$ .

Check. $72\div18=4$ and $72\div24=3$ : both bells complete a whole number of periods.

Now change only the second bell's period. Include a prime factor even when it belongs to just one period: both periods must divide the answer.

Worked example 6: include an unshared prime

Question. Two bells ring every $18$ minutes and every $40$ minutes. They both ring at $10{:}00$ . At what time do they next ring together?

Plan. Include all required prime powers, then convert the interval to hours.

\begin{aligned} 18&=2\times3^2,\qquad40=2^3\times5 &&\text{factorise the periods}\\ \operatorname{LCM}(18,40)&=2^3\times3^2\times5 &&\text{include every needed prime}\\ &=360 &&\text{multiply the selected powers}\\ 360\,\mathrm{min}&=6\,\mathrm{h} &&\text{divide by sixty} \end{aligned}

Why include both $3^2$ and $5$ ? One is needed for divisibility by $18$ , the other for divisibility by $40$ .

Answer. They next ring together at $16{:}00$ .

Check. $360\div18=20$ and $360\div40=9$ , both whole numbers of periods.

A useful surprise links HCF and LCM for any two positive integers: their product equals the product of the original integers. For $18$ and $24$ , the HCF is $6$ and the LCM is $72$ , so $6\times72=18\times24=432$ . Each prime's smaller index goes into the HCF and its larger index into the LCM; together they use exactly the indices in the two original numbers. This is a useful check, not a replacement for deciding what the question asks.

Watch out

Wrong: the next shared interval for periods $18$ and $24$ is their HCF, $6$ minutes. Neither full period has elapsed then. Use their LCM, $72$ minutes, which is divisible by both periods.

The opening bead problem asked for a number that divides both totals, so it used HCF: $42$ identical packs. A next shared event asks for a multiple of both periods, so it uses LCM.

Quick Recap

Split factors until every end value is prime, then collect repeated primes into powers.
HCF uses shared primes with the smallest indices and divides each original number.
LCM uses all needed primes with the largest indices and is a multiple of each original number.
Check whether the question asks for equal groups or a shared repeat, then interpret the result in context.

The opening bead totals make at most $42$ identical packs, each with $2$ red beads and $3$ blue beads.

Last Accessed

Number

Algebra

Shape, space and measure

Handling data

1.4 - Prime factorisation, HCF and LCM

Products of prime powers

Highest common factor and equal groups

Lowest common multiple and repeating events

Quick Recap

Learn faster with Nova