Fundamental Theorem of Arithmetic

Every integer > 1 has a unique prime factorization.

The idea

Theorem (Fundamental theorem of arithmetic).

Every integer $n > 1$ can be written as a product of primes, and apart from the order of the factors there is only one such product.

The theorem makes two claims. Existence says that every integer above $1$ splits into primes at all. Uniqueness says that two people who factor the same $n$, however they choose to split it along the way, arrive at the same collection of primes. The figure shows two chains of splittings for one $n$ — first as $n = ab$, then as $n = cd$ — both ending at the same primes $p, q, r, s$, exactly as uniqueness demands.

Uniqueness is the deeper claim: nothing about splitting obviously prevents two chains from ending at different primes, and in some number systems that does happen. Its holding in the integers makes the factorization a fixed description of an integer: divisor counts and greatest common divisors can be read straight from it.

Ways to work on it

• Walkthrough. Existence (induction), uniqueness (Euclid's lemma), and where unique factorization fails.
• Proof. See why — existence by strong induction, uniqueness from Euclid's lemma (via Bezout).
• Practice. Factor a random integer into primes.
• Hardest. Compute / lcm from prime factorizations.

Not sure where to start? Take the ten-question placement test.