Prime Numbers and Factorisation

A prime number has exactly two factors — 1 and itself. Every composite number can be uniquely expressed as a product of prime numbers (prime factorisation).

Prime and Composite Numbers

Prime: exactly 2 factors — 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19…
Composite: more than 2 factors. Examples: 4, 6, 8, 9, 10, 12…
Special case: 1 is neither prime nor composite.

Note 2 is the only even prime number. All other even numbers are composite (divisible by 2).

Prime Factorisation

Every composite number can be broken down into a product of primes — its prime factorisation.

Method: Factor tree

$84 = 2 \times 42 = 2 \times 2 \times 21 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$

Method: Repeated division (ladder)

Divide repeatedly by the smallest prime that fits.

Using Prime Factorisation

GCD (Greatest Common Divisor) — take the lowest power of each shared prime:

$\text{GCD}(36, 48): \quad 36 = 2^2 \cdot 3^2, \quad 48 = 2^4 \cdot 3$

$\text{GCD} = 2^2 \cdot 3 = 12$

LCM (Lowest Common Multiple) — take the highest power of each prime:

$\text{LCM}(36, 48) = 2^4 \cdot 3^2 = 144$

1
Write the number
120
2
Divide by 2 (smallest prime)
120 ÷ 2 = 60 → 60 ÷ 2 = 30 → 30 ÷ 2 = 15
3
Divide by 3
15 ÷ 3 = 5
4
5 is prime — done
$120 = 2^3 \times 3 \times 5$

Find the LCM of 12 and 18.

$12 = 2^2 \times 3, \quad 18 = 2 \times 3^2$

$\text{LCM} = 2^2 \times 3^2 = 4 \times 9 = 36$

Real world: RSA encryption in cybersecurity

RSA encryption — used to secure every HTTPS website — works because multiplying two large primes (e.g. $p = 61$ , $q = 53$ ) gives a number ( $n = 3233$ ) that is very hard to factor back. Prime factorisation underpins the security of online banking and messaging apps.

Real world: simplifying engineering fractions

An engineer needs to simplify a gear ratio of $\frac{84}{120}$ . $\text{GCD}(84, 120) = 12$ , so the ratio simplifies to $\frac{7}{10}$ — meaning for every 7 turns of one gear, the other turns 10 times. Prime factorisation makes this calculation fast and reliable.

Tip A quick divisibility check: if the sum of a number's digits is divisible by 3, the number itself is divisible by 3. Use this to speed up factor trees.

Practice Problems

Write the prime factorisation of 72.

Show answer

72 = 8 × 9 = 2³ × 3².

Find the GCD of 60 and 90.

Show answer

60 = 2²×3×5, 90 = 2×3²×5. GCD = 2×3×5 = 30.

Is 97 prime?

Show answer

Yes — 97 is prime (not divisible by 2, 3, 5, 7).