Prime numbers and prime factorisation

A prime number has exactly two factors: $1$ and itself. The first few primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$.

Idea

Numbers that are not prime (and not $1$) are called composite. They can always be written as a product of primes , uniquely, in fact. This is the Fundamental Theorem of Arithmetic.

For example, $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$. There is only one way to write $60$ as a product of primes (apart from reordering).

How to find the prime factorisation of $n$:

1. Try the smallest prime ($2$). If it divides $n$, write it down and replace $n$ by $n / 2$. Repeat with $2$ until it no longer divides.
2. Try the next prime ($3$). Repeat.
3. Continue with $5, 7, 11, \dots$ until $n$ becomes $1$.

This is the factor tree or division ladder method.

For example, $84 \div 2 = 42$, $42 \div 2 = 21$, $21 \div 3 = 7$, $7 \div 7 = 1$. So $84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$.

Useful tips:

• If a number is even, $2$ is a factor.
• If the sum of digits is divisible by $3$, then $3$ is a factor.
• If it ends in $0$ or $5$, $5$ is a factor.

A number is prime if it has no prime factor less than or equal to its square root. So to check if $97$ is prime, you only need to test primes up to $\sqrt{97} \approx 9.8$, i.e., $2, 3, 5, 7$. None divides $97$. So $97$ is prime.

Worked examples

Example 1. Prime factorisation of $60$.

$60 \div 2 = 30; 30 \div 2 = 15; 15 \div 3 = 5; 5 \div 5 = 1$. So $60 = 2^2 \times 3 \times 5$.

Example 2. Prime factorisation of $144$.

$144 \div 2 = 72; \div 2 = 36; \div 2 = 18; \div 2 = 9; 9 \div 3 = 3; \div 3 = 1$. So $144 = 2^4 \times 3^2$.

Example 3. Is $51$ prime or composite?

Sum of digits: $5+1=6$, divisible by $3$. So $51 = 3 \times 17$. Composite.

Example 4. Prime factorisation of $315$.

$315 \div 3 = 105; \div 3 = 35; 35 \div 5 = 7; \div 7 = 1$. So $315 = 3^2 \times 5 \times 7$.

Try it yourself

1. Prime factorisation of $30$.
2. Prime factorisation of $72$.
3. Is $89$ prime?
4. Prime factorisation of $100$.
5. Prime factorisation of $225$.
6. Is $123$ prime?
7. Find the first prime greater than $50$.
8. Prime factorisation of $1000$.

Activity

Use the sieve of Eratosthenes: write numbers $1$ to $100$ in a grid. Cross out $1$, then multiples of $2$ (except $2$), of $3$ (except $3$), of $5$, of $7$. What's left are the primes up to $100$.