The Fundamental Theorem of Arithmetic

Why can every integer greater than 1 be broken into primes in essentially one way? Take the number 360. You might factor it as $2 \cdot 180 = 2 \cdot 4 \cdot 45 = 2 \cdot 2 \cdot 2 \cdot 45$ . Or start differently as $360 = 8 \cdot 45 = 8 \cdot 9 \cdot 5$ . Every route, if pushed all the way down to primes, ends at the same multiset $\{2,2,2,3,3,5\}$ . This is not an accident of small numbers. It is a theorem, and a surprisingly non-obvious one. Uniqueness fails in many number systems that look superficially similar to the integers. The Fundamental Theorem of Arithmetic (FTA) asserts two separate things. Every integer greater than 1 admits a factorization into primes (existence). Any two such factorizations agree up to the order of the factors (uniqueness). Existence is the easy half, provable by a short induction. Uniqueness is the deep half. Its standard proof rests entirely on Euclid's Lemma — the statement that a prime dividing a product must divide one of the factors. Without that lemma, uniqueness can genuinely fail. We will see this in rings where an analogue of "prime" exists but Euclid's Lemma does not hold. The theorem matters because it turns multiplicative questions about integers into combinatorial questions about exponent vectors of primes. Once you know $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ uniquely, several things follow. Computing $\gcd$ , $\mathrm{lcm}$ , the number of divisors, and multiplicative functions like Euler's totient all become exercises. They reduce to comparing or manipulating exponents. The FTA is the load-bearing wall of elementary number theory. Nearly every later structural result about divisibility either uses it directly or generalizes it to other rings. This article gives the precise statement and a complete non-circular proof of both halves. It includes a worked example tracking every step of an unequal factorization. It also gives a concrete counterexample showing what breaks in $\mathbb{Z}[\sqrt{-5}]$ when the analogue of Euclid's Lemma fails. It closes with the theorem's role in modern applications. These range from cryptographic key generation to the analytic machinery of the Riemann zeta function.

Key takeaways

Every integer $n > 1$ factors into primes: this is the existence half, proved by strong induction.
The uniqueness half says the prime factorization is the same multiset of primes no matter how you find it.
Uniqueness is proved using Euclid's Lemma: if a prime $p \mid ab$ then $p \mid a$ or $p \mid b$ .
The theorem fails to hold in some other number systems (e.g. $\mathbb{Z}[\sqrt{-5}]$ ), which shows Euclid's Lemma is not automatic.
FTA converts multiplicative problems (gcd, lcm, divisor counting) into additive problems on exponent vectors.
It underlies cryptographic assumptions (RSA) and the Euler product for the zeta function.
Key idea: primes are the multiplicative "atoms" of $\mathbb{Z}$ , and every integer decomposes into them in exactly one way.

Where this lives today

The Fundamental Theorem of Arithmetic is the quiet engine behind an enormous range of mathematics and its applications:

Cryptography. The security of RSA public-key encryption rests on the practical difficulty of factoring a large composite $n = pq$ into its two prime factors, even though the Fundamental Theorem guarantees that factorization exists and is unique — the theorem guarantees what the answer is, while computational hardness is about finding it quickly.
Analytic number theory. The Euler product formula

\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1-p^{-s}}, \qquad \Re(s)>1,

is a direct restatement of unique factorization: expanding the right side via geometric series and unique factorization shows every term $n^{-s}$ on the left arises from exactly one combination of prime powers on the right. This identity is the starting point for the analytic study of the Riemann zeta function and the distribution of primes.

Algebraic number theory and beyond. The failure of unique factorization in rings like $\mathbb{Z}[\sqrt{-5}]$ motivated the development of ideal theory and Dedekind domains, a cornerstone of modern algebraic number theory, algebraic geometry, and the study of class groups.
Computer science. Algorithms for integer factorization, primality testing, and computing gcd and lcm via Prime Factorization all take unique factorization as their conceptual foundation, even when the actual computation uses the Euclidean algorithm rather than factoring directly.
Combinatorics and multiplicative functions. Functions like the divisor-counting function, sum-of-divisors function, and Euler's Totient Function are all defined and computed via the exponents in a number's unique prime factorization, and their multiplicativity is a direct consequence of the theorem.

:::quiz[In $\mathbb{Z}[\sqrt{-5}]$ , the number 6 factors as both $2\cdot 3$ and $(1+\sqrt{-5})(1-\sqrt{-5})$ . What does this demonstrate?]

That $6$ is not actually composite in this ring
That existence of a factorization into irreducibles can hold while uniqueness fails ✓
That the norm function is not multiplicative
That $2$ and $3$ are units in this ring

Ask the tutor: How does unique factorization let us derive formulas for Euler's totient function directly from a number's prime exponents?

p > 1

Intuition

Think of the positive integers greater than $1$ as molecules and the primes as atoms. Multiplication combines atoms into molecules; factorization takes them back apart. The claim that factorization is unique is the number-theoretic analogue of saying a chemical compound has one determined atomic formula, not several inequivalent ones. This is far from automatic: in many other algebraic settings (systems of "numbers" built by adjoining roots like $\sqrt{-5}$ ), you can find irreducible elements that fail to play the role of atoms faithfully — the same "molecule" can be split into different irreducible pieces. What makes $\mathbb{Z}$ special is Euclid's Lemma, the mechanism that forces the split to be unique. A second useful picture is the lattice of exponent vectors. Fix a list of primes $2, 3, 5, 7, \dots$ . Every positive integer corresponds to a finite sequence of exponents $(a_1, a_2, a_3, \dots)$ , almost all zero, via $n = 2^{a_1}3^{a_2}5^{a_3}\cdots$ . Multiplying two integers corresponds to adding their exponent vectors coordinate-wise. The Fundamental Theorem of Arithmetic says this correspondence $n \leftrightarrow (a_1, a_2, a_3, \dots)$ is a bijection between positive integers and such vectors — the "coordinates" of an integer in prime-space are well defined.

Figure

The exponent-vector lattice for the prime basis

\{2,3,5\}

: each lattice point is a distinct integer, and factorization uniqueness means the map point → integer is injective

Central theorem

n

p

n

The proof technique for existence is strong induction with a splitting argument (reduce a composite number to two strictly smaller factors); the proof technique for uniqueness is strong induction driven by Euclid's Lemma, peeling off one matched prime at a time. Neither half of the proof invokes the Fundamental Theorem itself at any stage, so the argument is non-circular: existence uses only the definition of composite numbers, and uniqueness uses only Euclid's Lemma (a prerequisite result) together with existence's conclusion that a factorization exists to induct on.

Worked examples

Example 1: An asymmetric factorization, tracked step by step. Factor $n = 2\,3\,7\,11\,13 = 6006$ two different ways and confirm the theorem's uniqueness claim concretely. Route A (peel off small factors): $6006 = 2 \cdot 3003$ . Then $3003 = 3 \cdot 1001$ . Then $1001 = 7 \cdot 143$ . Then $143 = 11 \cdot 13$ . So

6006 = 2 \cdot 3 \cdot 7 \cdot 11 \cdot 13.

Route B (start from a different divisor): notice $6006 = 42 \cdot 143$ , since $42 \cdot 143 = 42\cdot 143 = 6006$ (check: $42 \cdot 100 = 4200$ , $42\cdot 43 = 1806$ , sum $= 6006$ ✓.) Now factor each piece: $42 = 2\cdot 3\cdot 7$ and $143 = 11 \cdot 13$ . So

6006 = (2\cdot 3\cdot 7)(11\cdot 13) = 2\cdot 3\cdot 7\cdot 11\cdot 13.

Route C (yet another split): $6006 = 66 \cdot 91$ . Check: $66\cdot 91 = 66\cdot 90 + 66 = 5940+66=6006$ ✓. Factor $66 = 2\cdot 3\cdot 11$ and $91 = 7\cdot 13$ . So

6006 = (2\cdot 3\cdot 11)(7\cdot 13) = 2\cdot 3\cdot 7\cdot 11\cdot 13.

All three routes, despite splitting the number completely differently at the first step ( $2$ vs. $42$ vs. $66$ as the first factor extracted), converge on the same multiset $\{2,3,7,11,13\}$ , exactly as the theorem guarantees. In canonical form,

6006 = 2^1 \cdot 3^1 \cdot 7^1 \cdot 11^1 \cdot 13^1.

Example 2: Using unique factorization to compute $\gcd$ and count divisors (foreshadowing <a class="wiki-link" href="/wiki/math-numthy-gcd-lcm-prime-factorization" data-track="wiki_article.body.wiki_link">gcd and lcm via Prime Factorization</a>). Let $a = 2^3 \cdot 3^2 \cdot 5 = 360$ and $b = 2^2 \cdot 3^4 \cdot 7 = 2268$ . Compute $\gcd(a,b)$ , $\mathrm{lcm}(a,b)$ , and the number of divisors of $a$ . First verify the numbers: $2^3\cdot 3^2 \cdot 5 = 8\cdot 9\cdot 5 = 360$ ✓, and $2^2 \cdot 3^4 \cdot 7 = 4\cdot 81\cdot 7 = 4\cdot 567 = 2268$ ✓. By the Fundamental Theorem, every prime factorization of a common divisor of $a,b$ can only use primes appearing in both $a$ and $b$ 's factorizations, namely $2$ and $3$ , and the exponent of each such prime in a common divisor cannot exceed its exponent in either $a$ or $b$ . Hence

\gcd(a,b) = 2^{\min(3,2)}\cdot 3^{\min(2,4)} = 2^2\cdot 3^2 = 4\cdot 9 = 36.

Similarly, a common multiple must contain each prime to at least the larger of the two exponents, and the least such multiple takes exactly the maximum exponent for every prime appearing in either number:

\mathrm{lcm}(a,b) = 2^{\max(3,2)}\cdot 3^{\max(2,4)}\cdot 5^{\max(1,0)}\cdot 7^{\max(0,1)} = 2^3\cdot 3^4\cdot 5\cdot 7 = 8\cdot 81\cdot 5\cdot 7.

Compute: $8\cdot 81 = 648$ , $648\cdot 5 = 3240$ , $3240\cdot 7 = 22680$ . So $\mathrm{lcm}(a,b) = 22680$ . Sanity check via $\gcd(a,b)\cdot \mathrm{lcm}(a,b) = a\cdot b$ : left side $36 \cdot 22680 = 816480$ ; right side $360\cdot 2268 = 816480$ ✓ (computing $360\cdot 2268 = 360\cdot 2000 + 360\cdot 268 = 720000+96480=816480$ ). Finally, the number of positive divisors of $a = 2^3\cdot3^2\cdot5^1$ is obtained because unique factorization makes every divisor of the form $2^{i}3^{j}5^{k}$ with $0\le i\le 3$ , $0\le j\le 2$ , $0\le k\le 1$ , giving

d(a) = (3+1)(2+1)(1+1) = 4\cdot3\cdot2 = 24

divisors, each corresponding to a distinct choice of exponents by uniqueness.

:::counterexample[Why Euclid's Lemma cannot be dropped: factorization into irreducibles in $\mathbb{Z}[\sqrt{-5}]$ ] The uniqueness half of the Fundamental Theorem was proved using Euclid's Lemma as an essential ingredient. Drop the hypothesis that this lemma holds, and uniqueness can fail even when existence of a factorization into irreducible elements still holds. Work in the ring $\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a,b \in \mathbb{Z}\}$ , with the usual addition and multiplication (and $\sqrt{-5}^2 = -5$ ). Define the norm $N(a+b\sqrt{-5}) = a^2+5b^2$ , which is multiplicative: $N(xy) = N(x)N(y)$ . Call a non-zero, non-unit element $\pi$ irreducible if whenever $\pi = xy$ , one of $x,y$ is a unit (the only units in this ring are $\pm 1$ , since $N(x)=1$ forces $a^2+5b^2=1$ , i.e. $b=0,a=\pm1$ ). Consider the number $6$ . It factors two ways:

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

Check the second: $(1+\sqrt{-5})(1-\sqrt{-5}) = 1 - (\sqrt{-5})^2 = 1-(-5) = 6$ ✓. Each of the four factors $2, 3, 1+\sqrt{-5}, 1-\sqrt{-5}$ is irreducible in $\mathbb{Z}[\sqrt{-5}]$ :

$N(2) = 4$ . If $2 = xy$ non-trivially, then $N(x)N(y)=4$ with neither factor $1$ , forcing $N(x)=N(y)=2$ . But $a^2+5b^2=2$ has no integer solutions (check $b=0\Rightarrow a^2=2$ impossible; $|b|\ge1 \Rightarrow 5b^2\ge5>2$ ). So $2$ is irreducible.
$N(3)=9$ ; a non-trivial factorization would need a factor of norm $3$ , and $a^2+5b^2=3$ has no integer solution by the same check. So $3$ is irreducible.
$N(1+\sqrt{-5}) = 1+5=6$ ; a non-trivial factorization would need factors of norm $2$ and $3$ (the only factor pairs of $6$ besides $1,6$ ), but norm $2$ is impossible as shown. So $1+\sqrt{-5}$ is irreducible. The same argument applies to $1-\sqrt{-5}$ .

So $6$ has two genuinely different factorizations into irreducibles, $2\cdot 3$ and $(1+\sqrt{-5})(1-\sqrt{-5})$ , and no unit multiple relates $2$ or $3$ to $1\pm\sqrt{-5}$ (their norms differ: $4, 9$ versus $6$ ), so these are not just the same factorization relabeled. Existence of a factorization into irreducibles still holds in this ring (a norm-descent argument analogous to the strong induction above works), but uniqueness fails. The reason it fails is precisely that Euclid's Lemma fails here: $2$ is irreducible but $2 \mid 6 = (1+\sqrt{-5})(1-\sqrt{-5})$ while $2$ divides neither $1+\sqrt{-5}$ nor $1-\sqrt{-5}$ (dividing would force an integer solution to a norm equation with no solutions, e.g. $N(2) = 4 \nmid N(1+\sqrt{-5})=6$ in the required divisibility sense). This single missing ingredient — Euclid's Lemma for irreducibles — is exactly what the uniqueness proof for $\mathbb{Z}$ used at its pivotal step, confirming that the hypothesis is essential, not merely convenient.

Scope, edge cases & common traps

Situation	What the theorem says	Common error
$n=1$	Not covered: $1$ has the empty product of primes, conventionally, but is not itself required to have a "prime factorization" in the sense of the theorem's statement	Treating $1$ as prime, or as requiring a nonempty factorization
$n$ prime	Factorization is the single factor $n$ itself	Thinking a prime "has no factorization"
Negative integers	Theorem as stated applies to $n>1$ ; extends to $\|n\|>1$ with a unit $\pm1$ prefactor	Forgetting the sign, e.g. claiming $-12$ and $12$ have "the same" factorization without the unit
Order of factors	Irrelevant — uniqueness is as a multiset / up to permutation	Treating $2\cdot3$ and $3\cdot2$ as different factorizations
Rings other than $\mathbb{Z}$	Uniqueness can fail without an analogue of Euclid's Lemma	Assuming all "number-like" rings have unique factorization automatically

Common trapThe classic error: assuming uniqueness is "obvious" from existence

Students often treat the Fundamental Theorem as a single easy fact and skip straight to using exponent vectors, without registering that uniqueness is a separate, non-trivial claim requiring Euclid's Lemma. The trap is subtle because for small numbers, uniqueness looks self-evident from trial division. But existence alone (every number breaks into irreducible pieces somehow) holds in many rings where uniqueness genuinely fails, as the $\mathbb{Z}[\sqrt{-5}]$ counterexample shows. Whenever you invoke "the" prime factorization of $n$ to define something (like $\gcd$ via minimum exponents), you are silently relying on the uniqueness half — always confirm the ring you're working in actually satisfies it, or restrict such definitions to $\mathbb{Z}$ where it is a theorem.

The mathematician behind it

Origins · 1 minEuclid of Alexandria and how this was discovered

Euclid of Alexandria

c. 300 BCE · Hellenistic mathematics, Ptolemaic Egypt

Euclid compiled the Elements, the most influential mathematics text in history, systematizing geometry and number theory into an axiomatic deductive structure. Book IX of the Elements contains Proposition 14, an early ancestor of the Fundamental Theorem of Arithmetic (restricted to certain cases), and Book VII contains what is now called Euclid's Lemma along with the Euclidean algorithm. Little is known of Euclid's life; he is thought to have taught at Alexandria's great library under Ptolemy I. His deductive method — deriving all results from a short list of explicit postulates — became the template for rigorous mathematics for over two thousand years, and the FTA's modern proof, resting on Euclid's Lemma, is a direct descendant of his own arguments.

History

- c. 300 BCE — Euclid's Elements, Book VII, states and proves the lemma that a prime dividing a product divides one of the factors, and Book IX gives partial factorization-uniqueness results.

- 1801 — Carl Friedrich Gauss, in Disquisitiones Arithmeticae, gives the first fully general and rigorous statement and proof of unique factorization for the integers, naming it explicitly as foundational.

- 1832 (published 1844) — Gauss extends unique factorization considerations to the Gaussian integers

\mathbb{Z}[i]

, showing the phenomenon generalizes to some, but not all, extended number systems.

- 1844 — Ernst Kummer, studying Fermat's Last Theorem, discovers that unique factorization fails in certain cyclotomic integer rings, motivating his invention of "ideal numbers" to restore a uniqueness statement.

- 1871 — Richard Dedekind formalizes Kummer's ideal numbers as ideals in general rings, launching the theory of Dedekind domains, where unique factorization is restored at the level of ideals even when it fails for elements.

Does the Fundamental Theorem of Arithmetic apply to the number 1?

No. The theorem as standardly stated applies to integers $n > 1$ . The number $1$ is conventionally treated as an "empty product" of primes (a product with zero factors), which is a useful bookkeeping convention (it makes multiplicativity of functions like the divisor-count function work cleanly), but $1$ is neither prime nor composite, and the theorem's existence and uniqueness claims are not asserted for it. Including $1$ as if it had a factorization with actual prime factors would also break uniqueness trivially, since $1 = 1\cdot 1 = 1\cdot1\cdot1=\cdots$ has no canonical form among primes.

Why does the theorem require primes specifically, rather than just "irreducible" numbers?

In the integers, "prime" (only divisible by $1$ and itself) and "irreducible" (cannot be written as a product of two smaller-than-itself positive integers) turn out to coincide, so the distinction is invisible in $\mathbb{Z}$ . In more general rings, they can differ: an irreducible element might not satisfy Euclid's Lemma. The uniqueness proof strictly needs the prime property (Euclid's Lemma-compatible), not merely irreducibility, which is exactly why unique factorization can fail in rings like $\mathbb{Z}[\sqrt{-5}]$ where elements are irreducible but not prime.

Is unique factorization true for negative integers too?

Yes, with a small adjustment. Every integer $n$ with $|n|>1$ can be written as $n = \pm p_1 p_2\cdots p_k$ for primes $p_i$ , and this is unique up to reordering the primes and up to the sign choice being forced by the sign of $n$ . Formally one says $\mathbb{Z}$ is a unique factorization domain where the units are $\pm 1$ , and factorizations are unique "up to units and order." The core content of the theorem, though, is entirely about the positive integers, since every integer's factorization reduces to that of its absolute value.

How does the Fundamental Theorem let you count the divisors of a number?

If $n = p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ is the unique factorization, then unique factorization guarantees that every positive divisor of $n$ has the form $p_1^{i_1}\cdots p_r^{i_r}$ with $0 \le i_j \le a_j$ , and different exponent tuples give different divisors. So the number of divisors is exactly the number of such tuples, $(a_1+1)(a_2+1)\cdots(a_r+1)$ . Without uniqueness, you could not be sure that every divisor arises this way, or that distinct tuples always give distinct divisors.

Can a number have infinitely many distinct prime factors?

No — every integer $n>1$ has only finitely many prime factors, and in fact at most $\log_2 n$ of them (with multiplicity), since each prime factor is at least $2$ and the product of $k$ factors each $\ge 2$ is at least $2^k$ , which must be $\le n$ . This finiteness is implicit in the existence proof: the induction terminates because the factors $d, e$ used at each splitting step are strictly smaller than $n$ , guaranteeing the recursive splitting process cannot continue forever.

Is the Fundamental Theorem of Arithmetic used to prove that there are infinitely many primes?

Not directly — the infinitude of primes (Euclid's other classical theorem) is logically independent of the FTA and is usually proved separately by contradiction (assuming a finite list of primes and constructing a number not divisible by any of them). However, the two results are often presented together because both underlie the basic structural picture of the integers: infinitude tells you there are infinitely many "atoms," while the FTA tells you how integers are built from those atoms uniquely.

What goes wrong in the proof if you only assume every irreducible splits products, i.e. weaken Euclid's Lemma to hold only for irreducibles times themselves?

The uniqueness proof's key inductive step needs the full strength of Euclid's Lemma applied to an arbitrary product of $m-1$ primes at once (via repeated application to pairs). If Euclid's Lemma held only in some restricted form — say only for a prime dividing a product of exactly two specific irreducibles rather than an arbitrary product — the inductive step matching $p_1$ to some $q_j$ among an arbitrary-length product $q_1\cdots q_m$ could fail, and the argument would break down exactly at the point where $p_1$ is shown to divide one particular $q_j$ .