The Fundamental Theorem of Arithmetic

⚡ Key Takeaways

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 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.

DefinitionPrime 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.

1

\quad n = p_1^{a_1}\, p_2^{a_2}\, p_3^{a_3} \cdots p_k^{a_k}

Derivation hint: collect repeated prime factors and write each distinct prime $p_i$ raised to the count $a_i \ge 1$ of how many times it appears; this is the canonical (or standard) prime factorization. Here $p_1 < p_2 < \cdots < p_k$ are distinct primes and each exponent $a_i$ is a positive integer.

TheoremFundamental Theorem of Arithmetic

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

2

\quad n = p_1\, p_2 \cdots p_m \qquad (p_i \text{ prime, not necessarily distinct}),

Derivation hint: 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

3

\quad n = p_1\, p_2 \cdots p_m = q_1\, q_2 \cdots q_r,

Derivation hint: 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)$ .

TheoremEuclid's Lemma

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

5

\quad p \mid ab \;\Longrightarrow\; p \mid a \ \text{ or }\ p \mid b.

Derivation hint: if $p \nmid a$ , then $\gcd(p,a)=1$ , so Bézout gives $px + ay = 1$ ; multiply by $b$ .

ProofExistence of a Prime Factorization

We use strong induction on $n \ge 2$ . 1. Base case. $n = 2$ is prime, so it is already a product of primes (a product of one prime). 2. Inductive step. Assume every integer $k$ with $2 \le k < n$ is a product of primes. Consider $n$ . 3. Case A — $n$ is prime. Then $n$ is itself a product of primes (trivially), and we are done. 4. Case B — $n$ is composite. Then $n = a \cdot b$ with $1 < a < n$ and $1 < b < n$ . 5. 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$ . 6. By induction, every integer $n > 1$ is a product of primes. $\blacksquare$

∎

ProofUniqueness 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

6

\quad n = p_1\, p_2 \cdots p_m = q_1\, q_2 \cdots q_r .

Derivation hint: minimal counterexample — assume two distinct factorizations exist and pick the least $n$ admitting them. 1. The prime $p_1$ divides $n = q_1 q_2 \cdots q_r$ . By Euclid's Lemma (applied repeatedly), $p_1$ divides some $q_j$ . 2. Since $q_j$ is prime, its only divisors are $1$ and $q_j$ . As $p_1 > 1$ , we must have $p_1 = q_j$ . 3. Reorder the $q$ 's so that $q_j = q_1$ . Cancel the common factor $p_1 = q_1$ from both sides:

7

\quad \frac{n}{p_1} = p_2 \cdots p_m = q_2 \cdots q_r .

Derivation hint: dividing $n$ by the shared prime yields a smaller integer with two factorizations inherited from $n$ . 4. 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. 5. Adding back $p_1 = q_1$ , the two factorizations of $n$ agree up to order — contradicting our assumption that they differed. 6. Therefore no such smallest counterexample exists, and factorization is unique up to order. $\blacksquare$

∎

⚠️ 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."

mathematician · 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.

🧠 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.

Figure

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

ExampleFactoring 360 and Counting Its Divisors

Given: $n = 360$ . Find its prime factorization and the number of positive divisors.

Steps: 1. Divide out 2's: $360 \div 2 = 180$ , $180 \div 2 = 90$ , $90 \div 2 = 45$ . So $2^3$ appears. 2. $45$ is odd; divide out 3's: $45 \div 3 = 15$ , $15 \div 3 = 5$ . So $3^2$ appears. 3. $5$ is prime. So $5^1$ appears. 4. Canonical form: $360 = 2^3 \cdot 3^2 \cdot 5^1$ . 5. The number of divisors of $n = p_1^{a_1}\cdots p_k^{a_k}$ is $(a_1+1)(a_2+1)\cdots(a_k+1)$ , because each prime's exponent may independently range from $0$ to $a_i$ . 6. Here: $(3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2$ .

8

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

Derivation hint: a divisor is a choice of exponent $0 \le e_i \le a_i$ for each prime; multiply the independent counts.

Answer: $\boxed{360 = 2^3 \cdot 3^2 \cdot 5, \quad d(360) = 24 \text{ divisors}}$

ExampleGCD and LCM via Prime Exponents

Given: $a = 84$ and $b = 90$ . Find $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ using factorizations.

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

9

\quad \gcd(84,90) = 2^1 \cdot 3^1 = 6.

Derivation hint: $v_p(\gcd) = \min(v_p(a),v_p(b))$ for every prime $p$ . 4. $\operatorname{lcm}$ : $2 \to \max(2,1)=2$ ; $3 \to \max(1,2)=2$ ; $5 \to 1$ ; $7 \to 1$ .

10

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

Derivation hint: $v_p(\operatorname{lcm}) = \max(v_p(a),v_p(b))$ ; note $\gcd \cdot \operatorname{lcm} = ab$ since $\min + \max =$ sum of exponents.

Check: $6 \cdot 1260 = 7560 = 84 \cdot 90$ . ✓

Answer: $\boxed{\gcd = 6, \quad \operatorname{lcm} = 1260}$

⚠️ 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).

CounterexampleUnique Factorization Can Fail

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

11

\quad 6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}).

Derivation hint: expand $(1+\sqrt{-5})(1-\sqrt{-5}) = 1 - (-5) = 6$ ; check that $2,3,1\pm\sqrt{-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 $\mathbb{Z}$ is Euclid's Lemma, which fails in $\mathbb{Z}[\sqrt{-5}]$ .

connection

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 $\sqrt{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 $\mathbb{Z}$ . Finally, Euclid's Lemma and Bézout's Identity are the logical machinery that powers the uniqueness half.

🔬 Where this appears

⏳ History

- ~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.

open-problem

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 $\mathbb{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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also