Engineering / Mathematics — Integer Foundations
Unique Factorization of the Integers
The fundamental theorem of arithmetic: existence and uniqueness of prime factorisation, and why the uniqueness half is the difficult one.
Executive summary
Every integer greater than 1 factors into primes, and does so in exactly one way up to order. The first half is an easy induction; the second required Euclid's lemma and, through it, the entire theory of greatest common divisors.
The theorem is so familiar that its content is easy to underrate. Unique factorisation fails in closely related number systems, and the failures are not exotic.
Learning objectives
- State the fundamental theorem of arithmetic precisely.
- Explain why uniqueness requires Euclid's lemma.
- Recognise number systems in which unique factorisation fails.
01The theorem
Fundamental theorem of arithmetic
Every integer n > 1 can be written as a product of primes
n = p₁^e₁ · p₂^e₂ ··· pₖ^eₖ
with distinct primes p₁ < ... < pₖ and positive exponents, and this representation is unique.
Existence is an induction on n. If n is prime there is nothing to do; otherwise n = ab with both factors strictly between 1 and n, and each factors by the inductive hypothesis.
Uniqueness is where the work is. Suppose an integer had two distinct prime factorisations. Cancel any primes common to both. A prime p remaining on the left divides the product on the right, so by Euclid's lemma it divides one of the primes there — forcing it to equal that prime, contradicting the cancellation.
02Where unique factorisation fails
The theorem is not a formal consequence of having a notion of multiplication. It is a genuine property of the integers, and adjacent systems lack it.
This is why algebra distinguishes irreducible elements — those with no non-trivial factorisation — from prime elements — those satisfying Euclid's lemma. In the integers the two notions coincide. In general they do not, and unique factorisation holds exactly when they do.
03Consequences and computational reality
Once available, unique factorisation makes several quantities computable in principle from the factorisation.
| Quantity | From the factorisation |
|---|---|
| Number of divisors | ∏(eᵢ + 1) |
| Sum of divisors | ∏(pᵢ^(eᵢ+1) − 1)/(pᵢ − 1) |
| Euler's phi | n · ∏(1 − 1/pᵢ) |
| gcd | min of exponents, prime by prime |
| lcm | max of exponents, prime by prime |
This gap between structural availability and computational accessibility is the defining tension of the subject, and it is what public-key cryptography monetises.
04Frequently asked questions
Why does the theorem exclude 1?
Because 1 is a unit and the empty product convention already covers it: 1 is the product of no primes. Including it as a prime would destroy uniqueness, since arbitrary powers of 1 could be inserted into any factorisation.
Is irreducible the same as prime?
In the integers, yes. In a general integral domain, prime implies irreducible but not conversely, and unique factorisation holds exactly in those domains where the two coincide. Z[√−5] is the standard counterexample.
If factorisation is hard, why is the theorem useful?
Because it licenses reasoning about integers structurally without computing anything. Proofs about multiplicative functions, about the distribution of divisors, and about the structure of the group of units all use the factorisation as an object of thought rather than a computed quantity.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 8-12.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.