Mathematics.

prime factorization

Fundamental Theorem of Arithmetic

Number Theory30 minDifficulty4 out of 10

You should know: prime numbers

Overview

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, up to the order the factors are listed. This uniqueness is what makes primes the 'atoms' of multiplication — every whole number has one, and only one, prime 'chemical formula'.

Intuition

Just as every molecule breaks down into a unique combination of atoms, every integer greater than 1 breaks down into a unique combination of prime factors. 12 is always 2×2×3 — never 2×2×3 in one calculation and something else (like 2×6) as its FINAL prime breakdown, because 6 itself isn't prime and must be broken down further.

Formal Definition

Definition

Every integer n > 1 can be written as:

n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}

Where p₁ < p₂ < ... < pₖ are distinct primes and eᵢ ≥ 1

Prime factorization
This representation is unique up to the order of the factors\text{This representation is unique up to the order of the factors}

Derivation

The proof splits into two parts: existence (by strong induction) and uniqueness (via Euclid's lemma):

Existence: if n is prime, done. Otherwise n=ab with 1<a,b<n; apply induction to a,b.\textbf{Existence: } \text{if } n \text{ is prime, done. Otherwise } n=ab \text{ with } 1<a,b<n; \text{ apply induction to } a, b.
Uniqueness: if p∣ab for prime p, then p∣a or p∣b (Euclid’s lemma)\textbf{Uniqueness: } \text{if } p \mid ab \text{ for prime } p, \text{ then } p\mid a \text{ or } p \mid b \text{ (Euclid's lemma)}
Comparing two factorizations of n term by term via Euclid’s lemma forces them to match\text{Comparing two factorizations of } n \text{ term by term via Euclid's lemma forces them to match}

Theorems

Theorem 1: Euclid's Lemma
If a prime p divides ab, then p divides a or p divides b.\text{If a prime } p \text{ divides } ab, \text{ then } p \text{ divides } a \text{ or } p \text{ divides } b.

Applications

RSA cryptography relies on the difficulty of reversing prime factorization for large numbers, a direct consequence of uniqueness giving every number one specific 'lock'.

Worked Examples

  1. Divide by successive primes.

    84=22×3×784 = 2^2 \times 3 \times 7

Answer: 2² × 3 × 7

Practice Problems

Difficulty 4/10

Find the prime factorization of 360.

Common Mistakes

Common Mistake

Thinking 1 has a prime factorization (or is itself prime).

1 is neither prime nor composite — the theorem applies only to integers greater than 1. Including 1 as a 'factor' would destroy uniqueness (n = n×1 = n×1×1 = ...).

Historical Background

The existence of a prime factorization was known to Euclid (Elements, Book VII-IX, c. 300 BCE), but the UNIQUENESS of that factorization was not rigorously proven until Carl Friedrich Gauss's Disquisitiones Arithmeticae in 1801, which gave the theorem its modern, complete statement and proof.

  1. c. 300 BCE

    Euclid proves every integer >1 has a prime factorization

    Euclid

  2. 1801

    Gauss proves uniqueness rigorously in Disquisitiones Arithmeticae

    Carl Friedrich Gauss

Summary

  • Every integer greater than 1 has a prime factorization, and it's unique up to ordering.
  • Primes act as the 'atoms' of multiplication.
  • Uniqueness rests on Euclid's Lemma: if a prime divides a product, it divides one of the factors.
  • GCD/LCM and modern cryptography (RSA) both depend directly on this uniqueness.

References

  1. WebsiteWikipedia — Fundamental theorem of arithmetic