Primes, HCF and LCM: Quick Revision

A brief note on Primes, HCF and LCM. Read it before a test. Try each question at the end before you open its answer.

Primes and the Fundamental Theorem

• A prime has exactly two factors. $1$ is neither prime nor composite.
• A factor tree or repeated division breaks a number into primes. Write repeats as powers: $840 = 2^3 \times 3 \times 5 \times 7$.
• The Fundamental Theorem of Arithmetic: every composite number is a product of primes in exactly one way, apart from the order.
• A number ends in $0$ only if its primes include both $2$ and $5$. So $6^n$, with primes $2$ and $3$ only, never ends in $0$.

The HCF and the LCM

• HCF: the primes common to all the numbers, each with its smallest power.
• LCM: every prime that appears, each with its greatest power.
• For two numbers only: HCF $\times$ LCM $= a \times b$.
• The HCF divides the LCM. Co-prime numbers have HCF $1$, and their LCM is their product.

Which one does a problem want?

• The largest equal size that fits exactly (pieces, tiles, containers): the HCF.
• The first time things happen together again (bells, lights, buses): the LCM.
• A remainder: take it away from each number for an HCF, or add it to the LCM.

Euclid's division method

Divide, then divide the divisor by the remainder, and go on. The last divisor before a remainder of $0$ is the HCF. It works because $a = b \times q + r$ gives HCF$(a, b) =$ HCF$(b, r)$. In Python, math.gcd(a, b) gives the HCF.

A worked example

Find the HCF and the LCM of $126$ and $150$, and check them.

1. Factorise. $126 = 2 \times 3^2 \times 7$ and $150 = 2 \times 3 \times 5^2$.
2. HCF. Common primes $2$ and $3$, smaller powers: $2 \times 3 = 6$.
3. LCM. All primes, greater powers: $2 \times 3^2 \times 5^2 \times 7 = 3150$.
4. Check. $6 \times 3150 = 18\,900$ and $126 \times 150 = 18\,900$.

Practice with new numbers

A program to try

Three buses leave a depot together at 6:00 a.m. and return every $16$, $20$ and $30$ minutes. The program finds when all three meet again, through the day.

Mistakes to avoid

• Calling 1 a prime. It has only one factor.
• Stopping at a composite factor. $840 = 8 \times 105$ is not yet the prime factorisation.
• Swapping the powers. Smallest powers for the HCF, greatest for the LCM.
• The product rule for three numbers. It holds for two numbers only.
• Mixed units. Change metres to centimetres before you find an HCF.

Check yourself

1. Asha cuts ribbons of $84\ \text{cm}$ and $98\ \text{cm}$ into equal pieces, as long as possible, with nothing left over. How long is each piece, and how many pieces are there?

2. The HCF of two numbers is $1$. What is their LCM?

3. Two clocks chime every $25$ minutes and every $40$ minutes. They chime together at noon. When do they next chime together?

4. In Euclid's method, why may we replace the pair $(a, b)$ by $(b, r)$?

5. What is the smallest number that both $14$ and $21$ divide?