Prime Factorisation

Prime factorisation: the fingerprint every number has exactly one of

Every whole number above 1 is a product of primes, and — this is the part that makes it useful — it is that product in only one way. The fundamental theorem of arithmetic guarantees the factorisation is unique, which is why it works as a fingerprint and why so much else, from simplifying fractions to public-key cryptography, is built on top of it.

How it works

• Splits a number into its prime factors, shown in exponent form and written out in full.
• Counts the divisors without listing them, straight from the exponents.
• Says whether the number is prime, which is simply the case where it factorises into itself.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Worked example

Factorising 360 by dividing out the smallest prime that fits, repeatedly.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5, and no other combination of primes multiplies to 360. From the exponents alone the divisor count follows: (3+1)(2+1)(1+1) = 24, because any divisor picks 0 to 3 twos, 0 to 2 threes and 0 or 1 five.

Reading the result

• The divisor formula is worth knowing on its own. You never have to list divisors to count them — add one to each exponent and multiply, because building a divisor means choosing independently how many of each prime to include.
• Trial division only needs to test up to the square root. If n has a factor larger than √n it must also have the matching one below it, so once you pass the square root there is nothing left to find. That is why factorising a six-digit number is instant.
• The tool steps in sixes after 2 and 3, checking only 6k−1 and 6k+1. Every other residue is divisible by 2 or 3 already, which skips two thirds of the candidates for free.
• That factorising is hard for very large numbers is a feature, not a limitation of this tool. RSA depends on multiplying two large primes being easy while recovering them is not — the asymmetry is the whole security argument.

Common questions

Is 1 prime?

No, and excluding it is a deliberate choice rather than an oversight. If 1 counted as prime, factorisations would stop being unique — 6 could be 2×3, or 1×2×3, or 1×1×2×3 — and the theorem that makes factorisation useful would need an awkward exception in every statement.

Why does my number factorise into just itself?

Because it is prime. A prime has no divisors other than 1 and itself, so its factorisation is a single term with exponent one. The tool says so explicitly rather than leaving you to infer it from a one-item list.