The Fundamental Theorem of Arithmetic: Unique Factorization

Every integer greater than 1 has exactly one prime factorization.

Not "at least one." Exactly one. 12 = 2² × 3. That's it. You can't find different primes that also multiply to 12. You can reorder (3 × 2² = 12), but the primes and their powers are fixed.

Every number has a unique prime fingerprint.

That's the unlock. The Fundamental Theorem of Arithmetic says multiplication has a definite structure: primes combine to form composites, and there's only one way to decompose a composite back into primes. This is why we can meaningfully ask "what are the prime factors of n?" — there's a unique answer.

The Theorem

Existence: Every integer n > 1 is either prime or a product of primes.

Uniqueness: This prime factorization is unique, up to the order of the factors.

Together: every integer > 1 can be written as

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

where the pᵢ are distinct primes and the aᵢ are positive integers. This representation is unique.

Examples

12 = 2² × 3 60 = 2² × 3 × 5 100 = 2² × 5² 1001 = 7 × 11 × 13 2310 = 2 × 3 × 5 × 7 × 11

Each factorization is the only one.

Why Existence?

Every composite can be broken down into smaller factors.

Take n. If n is prime, we're done. If not, n = a × b where 1 < a, b < n.

Now factor a and b. Repeat.

Since the factors keep getting smaller and stay positive integers, this process must terminate. The terminal factors are primes (they can't be broken down further).

So n is a product of primes. ∎

Why Uniqueness?

This is the hard part. Uniqueness requires a key lemma:

Euclid's Lemma: If a prime p divides ab, then p divides a or p divides b.

This is what makes primes special. Composites don't have this property: 6 | (4 × 9) = 36, but 6 ∤ 4 and 6 ∤ 9.

With Euclid's Lemma, suppose n has two factorizations:

n = p₁ × p₂ × ... × pᵣ = q₁ × q₂ × ... × qₛ

p₁ divides the left side, so p₁ divides the right side.

By Euclid's Lemma (applied repeatedly), p₁ divides some qⱼ.

But qⱼ is prime, so p₁ = qⱼ.

Cancel p₁ from both sides. Repeat.

All primes match up. The factorizations are the same. ∎

Prime Factorization Notation

We often write n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ with p₁ < p₂ < ... < pₖ.

360 = 2³ × 3² × 5

This canonical form lists primes in increasing order. It's the standard representation.

GCD and LCM from Factorizations

Given factorizations, GCD and LCM are easy:

a = 2³ × 3² × 5 b = 2 × 3³ × 7

GCD: Take the minimum power of each common prime. gcd(a, b) = 2¹ × 3² = 18

LCM: Take the maximum power of each prime that appears. lcm(a, b) = 2³ × 3³ × 5 × 7 = 7560

This gives the beautiful relation: gcd(a,b) × lcm(a,b) = a × b.

Counting Divisors

If n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ, how many divisors does n have?

Any divisor has the form p₁^f₁ × p₂^f₂ × ... × pₖ^fₖ where 0 ≤ fᵢ ≤ eᵢ.

For each pᵢ, there are (eᵢ + 1) choices for fᵢ.

Number of divisors = (e₁ + 1)(e₂ + 1)...(eₖ + 1)

Example: 360 = 2³ × 3² × 5¹ Divisors: (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24

Why "Fundamental"?

The theorem is fundamental because:

1. It establishes primes as building blocks
2. It makes factorization well-defined
3. It enables algorithms (GCD, LCM, divisor counting)
4. It underlies modular arithmetic, cryptography, and more

Without uniqueness, number theory would collapse. Questions like "is n divisible by p?" wouldn't have clean answers.

Factorization Is Hard

Finding the factorization of a large number is computationally difficult.

For n with hundreds of digits, no known algorithm factors n in polynomial time.

This difficulty is the foundation of RSA cryptography. The security of your encrypted messages depends on the hardness of factoring.

(Note: proving the factorization exists is easy. Computing it for large n is hard.)

Where Uniqueness Fails

In some number systems, unique factorization fails!

In ℤ[√-5] = {a + b√-5 : a, b ∈ ℤ}:

6 = 2 × 3 = (1 + √-5)(1 - √-5)

Two different factorizations into "irreducible" elements. Unique factorization fails.

This failure led to the development of ideals in algebraic number theory — a profound generalization.

The Core Insight

The Fundamental Theorem says: integers have unique prime DNA.

Every integer > 1 breaks down into primes in exactly one way. This structure — unique factorization — is what makes the integers special.

Primes are the alphabet. Factorization is spelling. Each number has a unique spelling. That's the theorem, and that's why it's fundamental.

Part 3 of the Number Theory series.

Previous: Prime Numbers: The Atoms of Arithmetic Next: Divisibility Rules: Patterns in the Digits