Singapore-Cambridge O-Level Mathematics

## Prime numbers and prime factorisation A **prime number** is a whole number greater than 1 whose only factors are 1 and itself. The first few are 2, 3, 5, 7, 11, 13, 17, 19, 23. The number 2 is the only even prime, and 1 is not prime because it has only one factor. A whole number greater than 1 that is not prime is **composite**. Every composite number can be written as a product of primes in exactly one way (apart from the order), and this is its **prime factorisation**. To find it, divide repeatedly by the smallest prime that goes in, and stop when the quotient is 1. $$ \begin{aligned} 360 \div 2 &= 180 \\ 180 \div 2 &= 90 \\ 90 \div 2 &= 45 \\ 45 \div 3 &= 15 \\ 15 \div 3 &= 5 \\ 5 \div 5 &= 1 \end{aligned} $$ So $360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5$. A factor tree gives the same result: split the number into any two factors, then keep splitting until every branch ends in a prime. To test whether a number $n$ is prime, it is enough to try the primes up to $\sqrt{n}$, because any factor pair has one member no larger than $\sqrt{n}$. For 97 the primes to try are 2, 3, 5 and 7, none of which divides it, so 97 is prime. ## Highest common factor The **highest common factor (HCF)** of two or more numbers is the largest whole number that divides exactly into all of them. Writing each number as a product of primes makes it easy to find: take each prime that appears in every number, raised to the lowest power it has in any of them. For…