Fundamental Theorem of Arithmetic

6 min read#number-theory

Every integer greater than 1 is a product of primes in exactly one way, up to the order of the factors.

Contents

Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic says that every integer greater than 1 can be written as a product of primes, and — crucially — that this factorization is unique apart from reordering. The number 60 is 2^2 \times 3 \times 5, and there is no other set of primes whose product is 60. This is what justifies calling primes the atoms of multiplication: just as molecules decompose into elements in one definite way, integers decompose into primes in one definite way.

n \;=\; p_1^{a_1}\,p_2^{a_2}\cdots p_k^{a_k}, \qquad p_1 < p_2 < \cdots < p_k \text{ prime}
(1)

Written in this canonical form — primes in increasing order with their exponents — the factorization is literally one of a kind. Two integers are equal if and only if their canonical forms match exponent for exponent.

Build the tree

Any factorization can be grown as a factor tree: split the number into any two factors, then keep splitting the composite ones until only primes remain at the leaves. Start from different splits and the tree looks different — but the multiset of leaves is always the same.

A factor tree for n. Composite nodes (blue) split into two factors; prime leaves glow green. Click to grow a tree for a new number — however you split, the prime leaves are always the same multiset.

Why uniqueness is the hard part

That every number factors into primes is easy: keep pulling out a factor until you can't. The deep claim is that the result is unique. The proof rests on Euclid's lemma:

Uniqueness is not automatic — it can fail in other number systems. Among the numbers of the form a + b\sqrt{-5}, the integer 6 factors two genuinely different ways, 6 = 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}), and neither factorization refines the other. That such worlds exist is exactly why the ordinary integers' unique factorization is a theorem worth naming.

Reading a number from its primes

The canonical form is a fingerprint that makes many quantities instantly computable. If n = p_1^{a_1}\cdots p_k^{a_k}, then the number of divisors of n is simply

d(n) = (a_1+1)(a_2+1)\cdots(a_k+1),

because each prime p_i may appear in a divisor anywhere from 0 to a_i times. For n = 60 = 2^2\cdot 3\cdot 5 that gives (2{+}1)(1{+}1)(1{+}1) = 12 divisors. The same fingerprint feeds the Greatest Common Divisor (take the smaller exponent of each shared prime) and Euler's Totient Function.

Using its prime factorization 72 = 2³·3², how many positive divisors does 72 have?

See also