What Is Prime Factorisation? Every Number Has Exactly One Recipe

The claim has two halves that are proved separately. Existence says every number above one can be written as a product of primes, which follows from repeatedly splitting any number that is not prime into smaller factors until nothing can be split further. Uniqueness says there is only one such product for each number, apart from rearranging the factors, and that half is the substantial one. Uniqueness is easy to take for granted and is genuinely not automatic, since number systems exist that satisfy existence and fail uniqueness, where a number has two genuinely different factorisations into irreducible elements. That such systems exist is what makes the theorem informative rather than trivial, and the mathematics developed to handle the failure, including the notion of an ideal, grew directly out of attempts to repair proofs that had assumed uniqueness where it did not hold.

Once the factorisation of a number is known, a great deal follows immediately:

• •All divisors, since every divisor is built from the same primes at equal or lower powers
• •The greatest common divisor of two numbers, by taking the lower power of each shared prime
• •The lowest common multiple, by taking the higher power of each prime appearing in either
• •Whether a number is a perfect square, since that requires every exponent to be even
• •The number of divisors, from a direct formula on the exponents
• •Whether a fraction terminates as a decimal, which depends only on which primes divide the denominator

Knowing that a unique factorisation exists is entirely separate from being able to find it, and the gap between the two is enormous for large numbers. Trial division works for small numbers and becomes hopeless quickly, since checking divisors up to the square root of a number with hundreds of digits is beyond any conceivable computation. Better algorithms exist and remain far slower than the multiplication that produced the number in the first place, which is the asymmetry at the heart of the problem. Testing whether a number is prime is a different and much easier task, and efficient methods exist that determine primality without finding any factors, which surprises people who assume the two problems are related. That combination, easy multiplication, easy primality testing and hard factoring, is what public key cryptography was built on, and the security of a great deal of internet communication rests on the difficulty persisting.

For numbers small enough to handle by hand the procedure is mechanical and worth knowing. Divide repeatedly by two until the result is odd, then by three until it no longer divides, then by five, seven, eleven and so on through the primes, recording each success, and stop once the square of the current divisor exceeds what remains, because at that point whatever is left must itself be prime. The divisibility shortcuts speed this up considerably, since a number is divisible by three when its digits sum to a multiple of three, by four when its last two digits form one, by nine when the digit sum is a multiple of nine and by eleven when the alternating digit sum is. A factor tree records the process visually and is the usual classroom presentation. The method scales terribly, which is exactly the point that makes the subject interesting once the numbers grow large.

Treating primes as the building blocks raises the question of how many there are and how they are distributed, and both have famous answers. There are infinitely many, which Euclid proved by an argument still taught unchanged, showing that any finite list of primes can be used to construct a number not divisible by any of them. Their distribution thins out as numbers grow, and the prime number theorem describes how, giving the density of primes near a large number in terms of its logarithm. Beyond that the questions become hard quickly, with the distribution of primes connected to one of the most famous unsolved problems in mathematics, and with simple-sounding claims about pairs of primes differing by two, and about every even number being a sum of two primes, remaining unproved despite enormous effort and overwhelming numerical evidence.

Every whole number above one is a product of primes in exactly one way, and the uniqueness half has to be proved because number systems exist where it fails. From a factorisation you get all divisors, the greatest common divisor and the lowest common multiple immediately. Finding the factorisation of a large number is far harder than multiplying, and that asymmetry underpins public key cryptography.