Prime factorisation

Take 60 and break it apart: 60 = 6 · 10. The 6 splits further into 2 · 3, the 10 into 2 · 5. What remains is 60 = 2 · 2 · 3 · 5, a product made entirely of primes, and none of them can be broken down any further. A prime is a number with exactly two divisors, 1 and itself: 2, 3, 5, 7, 11 and so on. This works for every number from 2 upward: primes are the atoms of the number world, and prime factorisation shows you which atoms a number is built from.

The factor tree

The quickest route to a factorisation is a factor tree. Write the number at the top and split it into two factors, any two you like. If a factor is not yet prime, it gets two branches of its own, and the tree keeps growing downward. Once every end shows a prime, you are done: the leaves are the factorisation. The lovely part: whether you start 60 with 6 · 10 or with 4 · 15, you arrive at the same leaves 2, 2, 3 and 5 either way. If you prefer working without a tree, just divide again and again by the smallest prime that fits: 60 : 2 = 30, 30 : 2 = 15, 15 : 3 = 5, and the 5 is already prime. Along the way you divided by 2, 2 and 3, and together with the leftover 5 that gives 60 = 2 · 2 · 3 · 5.

Unique like a fingerprint

It is no accident that the same primes appear at the end every time. This is a famous theorem, the fundamental theorem of arithmetic. It says that every number greater than 1 has exactly one prime factorisation, as long as you ignore the order of the factors. 12 is 2 · 2 · 3 and nothing else, just as water always consists of two hydrogen atoms and one oxygen atom. That is also exactly why 1 does not count as a prime: if it were allowed to join in, 12 would also be 1 · 2 · 2 · 3 or 1 · 1 · 2 · 2 · 3, and the beautiful uniqueness would be gone. When a factor appears several times, powers keep things short: 24 = $2^3 \cdot 3$.

So what is it all for? The factorisation turns the greatest common divisor (gcd) and the least common multiple (lcm) into a reading exercise. Take 24 = 2 · 2 · 2 · 3 and 36 = 2 · 2 · 3 · 3. For the gcd you collect what both share: 2 · 2 · 3 = 12. For the lcm you take each prime as often as it appears in whichever factorisation contains more of it, so the 2 three times and the 3 twice: 2 · 2 · 2 · 3 · 3 = 72. No trial and error, no guessing. And one glimpse ahead: for huge numbers with hundreds of digits, factorising is practically impossible even for computers, and exactly this difficulty, as the basis of modern encryption, protects your messages every day.