The Fundamental Theorem of Arithmetic

One-line statement: 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 of the factors). Key result in words: Prime numbers are the indivisible "atoms" of multiplication, and each whole number has a unique chemical-like formula built from them. Where it applies: Number theory, cryptography, fraction arithmetic, abstract algebra, and any setting that relies on counting divisors. Who/when: Implicit in Euclid's Elements (~300 BCE); fully stated and proved by Carl Friedrich Gauss in Disquisitiones Arithmeticae (1801).

The Fundamental Theorem of Arithmetic (FTA), also called the unique factorization theorem, asserts that every integer $n > 1$ can be expressed as a product of prime numbers, and that this expression is unique except for the order in which the primes are written. The theorem has two distinct parts that must both be proved: existence (a factorization exists at all) and uniqueness (there is only one). It matters because it transforms vague questions about whole numbers into precise statements about their prime "building blocks," making the integers a kind of mathematical periodic table. A surprising fact: uniqueness fails in slightly larger number systems — for example, in the numbers of the form $a + b - 5$ — which is why mathematicians do not take this theorem for granted, even though it feels obvious for ordinary integers.

The Core Insight

Primes are the multiplicative atoms of the integers. Just as a chemist identifies a molecule by which atoms it contains and in what quantities, a number theorist identifies an integer by which primes divide it and with what exponents. The deep content is not merely that atoms exist, but that the recipe is unique — no integer can be assembled from two genuinely different bags of prime ingredients. Everything else in elementary number theory ultimately leans on this single guarantee.

Formal Statement

Prime and Composite Numbers

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ itself. An integer $n > 1$ that is not prime is composite; it has a divisor $d$ with $1 < d < n$ .

The number $1$ is defined to be neither prime nor composite — a convention chosen precisely so that the FTA can claim uniqueness.

n = p_{1}^{a_{1}} p_{2}^{a_{2}} p_{3}^{a_{3}} \dots p_{k}^{a_{k}}

⟳collect repeated prime factors and write each distinct prime

p_{i}

raised to the count

a_{i} \geq 1

of how many times it appears; this is the canonical (or standard) prime factorization.

Here $p_{1} < p_{2} < \dots < p_{k}$ are distinct primes and each exponent $a_{i}$ is a positive integer.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as a product of primes,

n = p_{1} p_{2} \dots p_{m} (p_{i} prime, not necessarily distinct),

⟳existence — repeatedly extract a prime divisor and recurse on the quotient until only primes remain.

and this representation is unique up to the order of the factors. That is, if

n = p_{1} p_{2} \dots p_{m} = q_{1} q_{2} \dots q_{r},

⟳uniqueness — set two supposed factorizations equal and show, prime by prime, that they must coincide.

with all $p_{i}, q_{j}$ prime, then $m = r$ and the list $(q_{1}, \dots, q_{r})$ is a rearrangement of $(p_{1}, \dots, p_{m})$ .

A compact way to encode uniqueness uses exponents: a positive integer $n$ corresponds to one and only one tuple of prime exponents.

n = p prime \prod p^{v_{p} (n)}, v_{p} (n) \geq 0,

⟳

v_{p} (n)

, the

p

-adic valuation, counts how many times

p

divides

n

; all but finitely many

v_{p} (n)

are zero.

Why It Holds / Derivation

The proof splits into two independent claims. Existence is an easy induction. Uniqueness rests on a single crucial lemma — Euclid's Lemma — which is the real engine of the theorem.

Euclid's Lemma

If a prime $p$ divides a product $ab$ , then $p$ divides $a$ or $p$ divides $b$ .

p ∣ ab ⟹ p ∣ a or p ∣ b .

⟳if

p ∤ a

, then

g cd (p, a) = 1

, so Bézout gives

p x + a y = 1

; multiply by

b

Existence of a Prime Factorization

We use strong induction on $n \geq 2$ .

Base case. $n = 2$ is prime, so it is already a product of primes (a product of one prime).

Inductive step. Assume every integer $k$ with $2 \leq k < n$ is a product of primes. Consider $n$ .

Case A — $n$ is prime. Then $n$ is itself a product of primes (trivially), and we are done.

Case B — $n$ is composite. Then $n = a \cdot b$ with $1 < a < n$ and $1 < b < n$ .

By the inductive hypothesis, both $a$ and $b$ are products of primes. Concatenating those two lists gives a product-of-primes expression for $n = ab$ .

By induction, every integer $n > 1$ is a product of primes. $■$

Uniqueness of the Prime Factorization

Suppose, for contradiction, that some integer has two different prime factorizations. By the well-ordering principle, let $n$ be the smallest such integer, with

n = p_{1} p_{2} \dots p_{m} = q_{1} q_{2} \dots q_{r} .

⟳minimal counterexample — assume two distinct factorizations exist and pick the least

n

admitting them.

The prime $p_{1}$ divides $n = q_{1} q_{2} \dots q_{r}$ . By Euclid's Lemma (applied repeatedly), $p_{1}$ divides some $q_{j}$ .

Since $q_{j}$ is prime, its only divisors are $1$ and $q_{j}$ . As $p_{1} > 1$ , we must have $p_{1} = q_{j}$ .

Reorder the $q$ 's so that $q_{j} = q_{1}$ . Cancel the common factor $p_{1} = q_{1}$ from both sides:

\frac{n}{p _{1}} = p_{2} \dots p_{m} = q_{2} \dots q_{r} .

⟳dividing

n

by the shared prime yields a smaller integer with two factorizations inherited from

n

The number $n / p_{1}$ is smaller than $n$ and now has two prime factorizations. But $n$ was the smallest integer with two distinct factorizations — so $n / p_{1}$ must have only one. Hence the lists $(p_{2}, \dots, p_{m})$ and $(q_{2}, \dots, q_{r})$ agree up to order.

Adding back $p_{1} = q_{1}$ , the two factorizations of $n$ agree up to order — contradicting our assumption that they differed.

Therefore no such smallest counterexample exists, and factorization is unique up to order. $■$

The Theorem Is Two Theorems

A common student error is to think the FTA is "obvious" because existence is easy. The genuinely deep statement is uniqueness, and it depends entirely on Euclid's Lemma. Without that lemma — i.e., in number systems where it fails — existence still holds but uniqueness collapses. Never conflate "a factorization exists" with "the factorization is unique."

Carl Friedrich Gauss | 1777–1855

Though unique factorization was used implicitly for two millennia, it was Gauss who, in Disquisitiones Arithmeticae (1801, written when he was 21), gave the first explicit and rigorous statement and proof, recognizing uniqueness as a theorem in need of justification rather than an obvious fact. Gauss's deeper motivation was to study factorization in more exotic number systems (such as the Gaussian integers $a + bi$ ), where he discovered that whether unique factorization holds is a delicate question. This investigation seeded the entire field of algebraic number theory, and the very surprise that unique factorization can fail is what makes the FTA a genuine result rather than a triviality.

Building Intuition

Think of building numbers with multiplication LEGO bricks, where each brick is a prime. To build $12$ , you snap together $2$ , $2$ , and $3$ . The FTA says two things. First, you can build any number $> 1$ this way (existence). Second — and this is the magic — there is essentially only one way to build each number; you can rearrange the bricks but you cannot swap in a different set. You will never find that $12$ also equals, say, $5 \times$ (something whole). The primes that "fit" $12$ are locked in: two $2$ 's and one $3$ , forever. This is why we can speak of the prime factorization, with a definite article.

A factor tree for 360, showing every path lands on the same primes

Worked Examples

Factoring 360 and Counting Its Divisors

Given:

n = 360

. Find its prime factorization and the number of positive divisors. Steps:

Divide out 2's: $360 \div 2 = 180$ , $180 \div 2 = 90$ , $90 \div 2 = 45$ . So $2^{3}$ appears.
$45$ is odd; divide out 3's: $45 \div 3 = 15$ , $15 \div 3 = 5$ . So $3^{2}$ appears.
$5$ is prime. So $5^{1}$ appears.
Canonical form: $360 = 2^{3} \cdot 3^{2} \cdot 5^{1}$ .
The number of divisors of $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ is $(a_{1} + 1) (a_{2} + 1) \dots (a_{k} + 1)$ , because each prime's exponent may independently range from $0$ to $a_{i}$ .
Here: $(3 + 1) (2 + 1) (1 + 1) = 4 \cdot 3 \cdot 2$ .

d (360) = (3 + 1) (2 + 1) (1 + 1) = 24.

⟳a divisor is a choice of exponent

0 \leq e_{i} \leq a_{i}

for each prime; multiply the independent counts.

Answer:

360 = 2^{3} \cdot 3^{2} \cdot 5, d (360) = 24 divisors

GCD and LCM via Prime Exponents

Given:

a = 84

and

b = 90

. Find

g cd (a, b)

and

lcm (a, b)

using factorizations. Steps:

Factor: $84 = 2^{2} \cdot 3^{1} \cdot 7^{1}$ and $90 = 2^{1} \cdot 3^{2} \cdot 5^{1}$ .
For each prime, the GCD takes the minimum exponent; the LCM takes the maximum.
$g cd$ : prime $2 \to min (2, 1) = 1$ ; prime $3 \to min (1, 2) = 1$ ; primes $5, 7 \to min (0, \cdot) = 0$ .

g cd (84, 90) = 2^{1} \cdot 3^{1} = 6.

⟳

v_{p} (g cd) = min (v_{p} (a), v_{p} (b))

for every prime

p

$lcm$ : $2 \to max (2, 1) = 2$ ; $3 \to max (1, 2) = 2$ ; $5 \to 1$ ; $7 \to 1$ .

lcm (84, 90) = 2^{2} \cdot 3^{2} \cdot 5 \cdot 7 = 1260.

⟳

v_{p} (lcm) = max (v_{p} (a), v_{p} (b))

; note

g cd \cdot lcm = ab

since

min + max =

sum of exponents.

Check:

6 \cdot 1260 = 7560 = 84 \cdot 90

. ✓ Answer:

g cd = 6, lcm = 1260

Common Misconceptions

Why 1 Cannot Be Prime

If $1$ were allowed as a prime, uniqueness would fail instantly: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ , and so on. Defining $1$ as neither prime nor composite is not arbitrary — it is forced by the demand that factorizations be unique. Likewise, the theorem only covers integers $n > 1$ ; the numbers $0$ and the negatives need separate handling (and $0$ has no prime factorization at all).

Unique Factorization Can Fail

In the number system $Z [- 5] = {a + b - 5 : a, b \in Z}$ , consider:

6 = 2 \cdot 3 = (1 + - 5) (1 - - 5) .

⟳expand

(1 + - 5) (1 - - 5) = 1 - (- 5) = 6

; check that

2, 3, 1 \pm - 5

are all "irreducible" (un-splittable) in this ring.

All four factors are irreducible and none is a unit multiple of another, so $6$ has two genuinely different factorizations. This proves the FTA is a real theorem about the ordinary integers, not a logical inevitability. The property that saves $Z$ is Euclid's Lemma, which fails in $Z [- 5]$ .

Connections

The FTA is the keystone connecting many topics. It validates the methods of Greatest Common Divisor and Least Common Multiple via the min/max-of-exponents rule. It underwrites all of Modular Arithmetic through structural results like the Chinese Remainder Theorem, which decomposes computations modulo $n$ into independent computations modulo each prime power $p^{a}$ . It is the foundation of Rational and Irrational Numbers — for instance, the irrationality of $2$ follows because squaring doubles every prime exponent, so a perfect square can never equal $2 \times$ a perfect square. In abstract algebra, rings where the FTA holds are called unique factorization domains (UFDs), generalizing the theorem far beyond $Z$ . Finally, Euclid's Lemma and Bézout's Identity are the logical machinery that powers the uniqueness half.

Real-World Applications

RSA Cryptography. Public-key encryption relies on the fact that multiplying two large primes is easy but factoring their product back into primes is computationally hard — security rests directly on the difficulty of inverting the FTA.
Hashing and Gödel numbering. Encoding a sequence $(a_{1}, a_{2}, \dots)$ as $2^{a_{1}} 3^{a_{2}} 5^{a_{3}} \dots$ creates a reversible, collision-free code precisely because factorization is unique; Gödel used this in his incompleteness proofs.
Fraction arithmetic. Reducing $\frac{84}{90}$ to lowest terms uses prime factorizations to cancel the common $2 \cdot 3 = 6$ , giving $\frac{14}{15}$ .
LCM scheduling. Finding when periodic events (gears, traffic-light cycles, planetary alignments) recur uses $lcm$ , computed from prime exponents.
Error-detecting codes & checksums. Modular schemes such as ISBN and barcode check digits rest on arithmetic mod a number whose prime structure governs their detection power.
Music and tuning theory. The clash between octaves ( $2^{n}$ ) and perfect fifths ( $3^{m}$ ) — the "Pythagorean comma" — is a statement that powers of 2 and 3 never coincide, a direct consequence of unique factorization.
Computer algebra systems. Symbolic simplification of integers and polynomials uses factorization algorithms whose correctness is guaranteed by unique factorization.

Historical Development

~300 BCE — Euclid. Elements, Book VII, Proposition 30 proves Euclid's Lemma, and Propositions 31–32 establish that every number is measured by some prime. Uniqueness is used implicitly but never stated as a separate theorem.
~300 BCE — Euclid (Book IX, Prop. 20). Proves there are infinitely many primes, confirming the "atoms" never run out.
~1000 CE — Islamic mathematicians (e.g., al-Farisi) extend Euclidean ideas on divisors and amicable numbers, working with factorizations.
1585 — Simon Stevin treats integers and their factor structures systematically in L'Arithmétique.
1801 — Carl Friedrich Gauss. Disquisitiones Arithmeticae (Article 16) gives the first explicit, rigorous statement and proof of unique factorization, treating it as a theorem requiring justification.
1830s–1840s — Ernst Kummer. Discovers that unique factorization fails for cyclotomic integers, blocking a "proof" of Fermat's Last Theorem and prompting deep reflection on the theorem's limits.
1847 — Kummer introduces "ideal numbers" to restore a form of unique factorization, launching algebraic number theory.
1871 — Richard Dedekind formalizes Kummer's ideas into the modern theory of ideals, giving unique factorization of ideals in rings of integers.
20th century — Unique Factorization Domains (UFDs) are abstracted in ring theory, identifying exactly which algebraic structures share the integers' good behavior.

Subtleties & Limits

While the FTA guarantees a unique factorization exists, it says nothing about how to find it efficiently. The integer factorization problem — given a large $n$ , produce its prime factors — has no known polynomial-time algorithm on classical computers, and the presumed hardness of this task underpins much of modern cryptography. Shor's quantum algorithm (1994) can factor in polynomial time on a quantum computer, so whether large-scale quantum factoring becomes practical is an open engineering frontier with enormous consequences. Separately, in number rings beyond $Z$ , the class number measures how badly unique factorization fails, and many questions about which rings are UFDs (and the behavior of class numbers as fields grow) remain active research. The FTA is thus a clean theorem sitting atop a vast, still-open landscape.