The fundamental theorem of arithmetic

Theorem

The fundamental theorem of arithmetic

T-075Home MU-207Threads number

Statement

Every integer \( n \gt 1 \) can be written as a product of primes, \( n = p_1 p_2 \cdots p_k \) with each \( p_i \) prime and \( k \geq 1 \); moreover this factorisation is unique up to the order of the factors: if \( n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l \) with all \( p_i, q_j \) prime, then \( k = l \) and there is a permutation \( \sigma \) of \( \{1,\dots,k\} \) with \( p_i = q_{\sigma(i)} \) for every \( i \). (Equivalently, writing \( n = \prod_{i=1}^{r} p_i^{e_i} \) with \( p_1 \lt p_2 \lt \cdots \lt p_r \) distinct primes and \( e_i \geq 1 \), the primes \( p_i \) and exponents \( e_i \) are uniquely determined by \( n \).)

Why it matters

The Fundamental Theorem of Arithmetic (FTA) is the reason "prime" is the right notion of atomic building block for the integers: it says the atoms exist (existence) and that the decomposition into atoms is not an accident of method (uniqueness). Every downstream tool of elementary number theory — computing \( \gcd \) and \( \mathrm{lcm} \) via exponent comparison, counting or summing divisors with multiplicative functions, proving irrationality of \( \sqrt{2} \), and defining \( p \)-adic valuations \( v_p(n) \) — silently assumes uniqueness. Without it, "the" prime factorisation would not be a well-defined object to reason about.

The theorem also draws a sharp boundary. It is a theorem, not a definition of the integers, and it fails in other rings that otherwise look very similar to \( \mathbb{Z} \) (see Fails without). Recognising exactly which structural properties of \( \mathbb{Z} \) make the proof work is what lets you predict, in a new ring, whether unique factorisation should be expected at all.

Hypotheses

The base ring is \( \mathbb{Z} \) (or, for the proof given, the positive integers with the usual order and division). In \( \mathbb{Z}[\sqrt{-5}] \), \( 6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) \) are two genuinely different factorisations into irreducibles, so the analogue of FTA fails; the proof below uses well-ordering of \( \mathbb{N} \) and the Euclidean algorithm, tools not available in every ring.

\( n \gt 1 \); the case \( n = 1 \) is excluded (empty product) and \( n \leq 0 \) is excluded (primes are defined only for positive integers, and factorisation into positive primes cannot reach a negative or zero number). If \( n = 1 \) were required to have a factorisation "into primes" with \( k \geq 1 \) factors, no such factorisation exists, since any product of one or more primes is \( \geq 2 \); this is why 1 is conventionally the empty product, not itself prime.

"Prime" means: \( p \gt 1 \) and the only positive divisors of \( p \) are \( 1 \) and \( p \) (irreducibility), and this coincides with the Euclid property "\( p \mid ab \Rightarrow p \mid a \) or \( p \mid b \)" only because of the proof below. If one instead worked in a ring where irreducibility and the Euclid property diverge (as in \( \mathbb{Z}[\sqrt{-5}] \), where \( 2 \) is irreducible but not prime since \( 2 \mid (1+\sqrt{-5})(1-\sqrt{-5}) \) while \( 2 \) divides neither factor), the uniqueness argument below breaks at Step 6.

Proof

Existence: every integer \( n \gt 1 \) is a product of one or more primes.

Strong induction on \( n \), base case \( n = 2 \) (prime, so it is the one-term product "itself"). A

Inductive step: assume every integer \( m \) with \( 2 \leq m \lt n \) is a product of primes. Either \( n \) is prime, in which case \( n \) itself is a one-term product of primes and we are done, or \( n \) is composite, so \( n = ab \) with \( 1 \lt a, b \lt n \).

Definition of composite: not prime and \( \gt 1 \) means it has a divisor strictly between \( 1 \) and itself, giving the factorisation \( n = ab \). A

By the inductive hypothesis applied to \( a \) and to \( b \) (both strictly smaller than \( n \) and \( \gt 1 \)), \( a = p_1 \cdots p_s \) and \( b = p_{s+1} \cdots p_{s+t} \) are products of primes, so \( n = p_1 \cdots p_{s+t} \) is a product of primes. This closes the induction: every \( n \gt 1 \) is a product of primes.

Strong induction: the hypothesis covers all integers below \( n \), and \( 1 \lt a,b \lt n \), so it legally applies to both. A

Lemma (Bézout's identity). For integers \( a, b \) not both zero, there exist integers \( x, y \) with \( ax + by = \gcd(a,b) \).

Proof cited: let \( S = \{ax+by : x,y \in \mathbb{Z}\} \cap \mathbb{Z}_{\gt 0} \), nonempty (contains \( |a| \) or \( |b| \)); by well-ordering \( S \) has a least element \( d = ax_0+by_0 \). Division with remainder shows \( d \mid a \) and \( d \mid b \) (else the remainder of dividing \( a \) by \( d \) would be a smaller positive element of \( S \)), and any common divisor of \( a,b \) divides \( d \), so \( d = \gcd(a,b) \). C

Lemma (Euclid's Lemma). If \( p \) is prime and \( p \mid ab \), then \( p \mid a \) or \( p \mid b \).

Suppose \( p \nmid a \). Since the only positive divisors of \( p \) are \( 1 \) and \( p \), and \( p \nmid a \), \( \gcd(p,a) = 1 \). By Step 4, \( px + ay = 1 \) for some integers \( x,y \). Multiply by \( b \): \( pbx + aby = b \). Now \( p \mid pbx \) trivially, and \( p \mid aby \) because \( p \mid ab \) by hypothesis; hence \( p \) divides the sum \( pbx+aby = b \). B

Corollary (extended Euclid's Lemma). If \( p \) is prime and \( p \mid q_1 q_2 \cdots q_l \), then \( p \mid q_j \) for some \( j \).

Induction on \( l \) using Step 5 repeatedly: \( p \mid q_1(q_2\cdots q_l) \) forces \( p \mid q_1 \) or \( p \mid q_2\cdots q_l \); in the second case recurse on the shorter product. A

Uniqueness setup: suppose, for contradiction, that some integer \( \gt 1 \) has two genuinely different prime factorisations, and let \( n \) be the smallest such integer, \( n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l \) with all factors prime and no rearrangement making the two lists equal termwise.

Well-ordering principle: a nonempty subset of \( \mathbb{Z}_{\gt 0} \) (the set of integers with a non-unique factorisation) has a least element, assuming it is nonempty. B

Since \( p_1 \mid n = q_1 q_2 \cdots q_l \), Step 6 gives \( p_1 \mid q_j \) for some \( j \); relabel so \( j = 1 \). But \( q_1 \) is prime, so its only divisors \( \gt 1 \) are itself; since \( p_1 \gt 1 \) and \( p_1 \mid q_1 \), we get \( p_1 = q_1 \).

Definition of prime applied to \( q_1 \): a divisor of \( q_1 \) exceeding 1 must equal \( q_1 \). B

Cancel \( p_1 = q_1 \) from both products (legal since \( \mathbb{Z} \) has no zero divisors and \( p_1 \neq 0 \)): \( n' := n/p_1 = p_2 \cdots p_k = q_2 \cdots q_l \). If \( k = 1 \) then \( n' = 1 \), forcing \( l = 1 \) too (a product of primes equal to 1 is impossible unless there are no factors), so the two original factorisations were already identical, a contradiction; hence \( k, l \geq 2 \) and \( 1 \leq n' \lt n \).

Cancellation law in an integral domain: \( p_1 x = p_1 y \wedge p_1 \neq 0 \Rightarrow x=y \). A

\( n' \lt n \) and \( n' \gt 1 \) has two prime factorisations \( p_2\cdots p_k \) and \( q_2 \cdots q_l \) which, by minimality of \( n \), must agree after some rearrangement (or \( n' \) has a unique one if it is prime itself). Reattaching \( p_1 = q_1 \) to both sides shows the original factorisations of \( n \) agree after rearrangement too — contradicting the choice of \( n \) as a counterexample.

Minimality of the counterexample \( n \) (Step 7): every integer strictly between \( 1 \) and \( n \) has a unique factorisation, since \( n \) was chosen least without this property. C

No counterexample exists: prime factorisation is unique up to order for every integer \( n \gt 1 \). Combined with Step 3, this proves the theorem.

Proof by contradiction (reductio): the assumption of Step 7 leads to a contradiction at Step 10, so it is false. A

Result

\[ \forall n \in \mathbb{Z}_{\gt 1},\ \exists!\, (p_1 \leq p_2 \leq \cdots \leq p_k) \text{ prime with } n = \prod_{i=1}^{k} p_i \]

Reading. Every integer bigger than 1 breaks into primes in exactly one way (once you agree to list the primes in increasing order, or equivalently to record them as a multiset). Primes really are the indivisible building blocks of the integers, and there is only one blueprint per integer.

Scope. Stated here for positive integers \( n \gt 1 \); extends verbatim to negative integers \( n \lt -1 \) by factoring \( |n| \) and carrying a sign unit \( \pm 1 \), and to any principal ideal domain (in particular any Euclidean domain), since Steps 4–11 only use: well-ordering / division with remainder (for Bézout), no zero divisors (for cancellation), and the definition of prime — all of which principal ideal domains supply. It does not automatically extend to arbitrary integral domains (see Fails without).

Corollaries & converses

Every \( n \gt 1 \) has a canonical form \( n = \prod_{i=1}^{r} p_i^{e_i} \), \( p_1 \lt \cdots \lt p_r \) primes, \( e_i \geq 1 \), unique in the \( p_i \) and \( e_i \); this defines the \( p \)-adic valuation \( v_p(n) := e_i \) if \( p = p_i \), else \( 0 \), and \( v_p \) is well-defined precisely because of uniqueness.
\( \gcd(m,n) = \prod_p p^{\min(v_p(m),v_p(n))} \) and \( \mathrm{lcm}(m,n) = \prod_p p^{\max(v_p(m),v_p(n))} \); these formulas presuppose FTA and are otherwise unjustified.
The number-of-divisors and sum-of-divisors functions \( d(n) = \prod_i (e_i+1) \), \( \sigma(n) = \prod_i \frac{p_i^{e_i+1}-1}{p_i-1} \) are multiplicative precisely because factorisation is unique, so distinct prime powers combine independently.
Converse-shaped statement: if \( n \) has a unique factorisation into irreducibles for the ordinary meaning of "irreducible", is \( n \) necessarily built from primes in the Euclid sense? In \( \mathbb{Z} \) yes, because Step 5 shows irreducible and prime coincide there; this equivalence itself is special to rings where FTA holds and cannot be assumed elsewhere.
There is no meaningful "converse" of FTA as an implication (it is an existence-and-uniqueness statement, not an if-then); the closest analogue, "if factorisation is unique then the ring is \( \mathbb{Z} \)", is false — many other rings (all PIDs) also have unique factorisation.

Fails without

Drop uniqueness of prime/irreducible coincidence (work in \( \mathbb{Z}[\sqrt{-5}] = \{a+b\sqrt{-5} : a,b \in \mathbb{Z}\} \)): \( 6 = 2 \times 3 = (1+\sqrt{-5})(1-\sqrt{-5}) \). One checks via the norm \( N(a+b\sqrt{-5}) = a^2+5b^2 \) that \( 2, 3, 1+\sqrt{-5}, 1-\sqrt{-5} \) are all irreducible (none factors further) and pairwise non-associate, so \( 6 \) has two structurally different factorisations into irreducibles. Step 5 (Euclid's Lemma) fails here: \( 2 \mid (1+\sqrt{-5})(1-\sqrt{-5}) = 6 \) but \( 2 \) divides neither factor, so \( 2 \) is irreducible without being prime.
Drop "prime" and allow units freely without fixing a convention (treat \( -1 \) as if it could be a genuine extra "prime factor" in \( \mathbb{Z} \)): \( 6 = 2 \cdot 3 = (-2)\cdot(-3) \) would look like two different factorisations if signs of primes were not pinned down; the standard fix is to state FTA for positive integers and positive primes only, exactly as this page does, which is why that restriction is a hypothesis and not a cosmetic choice.
Drop well-ordering / the ability to do division with remainder (work in a ring without a Euclidean-style algorithm, e.g. a general integral domain with no norm function): Bézout's identity (Step 4) has no proof, so Euclid's Lemma (Step 5) cannot be established, and the uniqueness argument (Steps 7–11) has no foothold even if existence of irreducible factorisations still holds by a separate finiteness argument.

Common errors

Treating "irreducible" (no proper factors) and "prime" (\( p \mid ab \Rightarrow p\mid a \) or \( p \mid b \)) as interchangeable by definition rather than as a coincidence that must be proved (Step 5); this is exactly the gap that breaks in \( \mathbb{Z}[\sqrt{-5}] \).
Forgetting the case split at the base of the induction and implicitly assuming \( n \) is composite in Step 2, silently mishandling the case where \( n \) is itself prime.
Believing FTA guarantees an efficient way to find the factorisation; existence and uniqueness say nothing about the computational cost of factoring, which is a separate (and, for large \( n \), hard) problem.
Applying the \( \gcd \)/\( \mathrm{lcm} \) exponent formulas from Corollaries to numbers without first confirming the setting is \( \mathbb{Z} \) (or a PID), then being surprised the identities fail in a ring like \( \mathbb{Z}[\sqrt{-5}] \).
Quoting "1 is not prime" as an arbitrary convention; it is forced by the theorem's uniqueness clause, since allowing 1 as a "prime" would let every factorisation be padded with arbitrarily many extra factors of 1, destroying uniqueness.

Discussion

FTA is often taken for granted because it is taught early, but historically it was not stated with full rigour until Gauss's Disquisitiones Arithmeticae (1801), even though Euclid's Elements (Book VII, roughly 300 BCE) already contains the key lemma (Step 5) and an existence argument. The gap between "Euclid's Lemma" and "unique factorisation as a named, universally stated theorem" is centuries wide, which is itself evidence that uniqueness is not obvious — it needed the cancellation/well-ordering machinery assembled explicitly.

The proof strategy generalises completely: any integral domain in which (a) every nonzero non-unit factors into irreducibles (an existence property, often from a suitable induction or a norm that strictly decreases), and (b) every irreducible is prime (Euclid's Lemma analogue, usually from Bézout's identity holding, i.e. the ring being a PID), is a Unique Factorisation Domain (UFD). \( \mathbb{Z} \), any field, \( k[x] \) for a field \( k \), and every PID are UFDs; \( \mathbb{Z}[\sqrt{-5}] \) is the standard first example of an integral domain that is not.

A cleaner high-level restatement: FTA says the monoid \( (\mathbb{Z}_{\gt 0}, \times) \) is isomorphic to the free commutative monoid on the set of primes, i.e. \( \mathbb{Z}_{\gt 0} \cong \bigoplus_{p \text{ prime}} \mathbb{Z}_{\geq 0} \) via \( n \mapsto (v_p(n))_p \). This is precisely the statement used to justify Euler's product formula \( \sum_{n=1}^{\infty} n^{-s} = \prod_p (1-p^{-s})^{-1} \) for \( \mathrm{Re}(s) \gt 1 \), the starting point of analytic number theory: expanding the right side as a geometric series in each factor and multiplying out reconstructs every \( n^{-s} \) exactly once, which is only valid because each \( n \) has exactly one prime signature.

Common misconception. Students sometimes think FTA is "trivial" because factoring small numbers by trial division always seems to land on the same answer; this confuses the (nontrivial) mathematical fact of uniqueness with the (unrelated) practical observation that trial division is deterministic. The theorem's content is that no method whatsoever, however different, can ever produce a genuinely different multiset of primes for the same \( n \) — a global uniqueness claim, not a comment on any specific algorithm.

Worked examples

Find \( \gcd(2520, 3300) \) and \( \mathrm{lcm}(2520,3300) \) using FTA.

Set up: factorise both numbers completely. A

\[ 2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7, \qquad 3300 = 2^2 \cdot 3 \cdot 5^2 \cdot 11 \]

Repeated trial division by primes \( 2,3,5,7,11,\dots \), justified as an existence procedure by Step 1–3 of the proof. A

Because factorisation is unique (Steps 7–11), the exponent vectors \( (3,2,1,1,0) \) and \( (2,1,2,0,1) \) over the prime list \( (2,3,5,7,11) \) are well-defined attributes of \( 2520 \) and \( 3300 \) — not artefacts of how the trial division happened to proceed.

This is exactly the content of the Corollary defining \( v_p \). B

\[ \gcd(2520,3300) = 2^{\min(3,2)}3^{\min(2,1)}5^{\min(1,2)}7^{\min(1,0)}11^{\min(0,1)} = 2^2\cdot3\cdot5 = 60 \]

gcd/lcm-via-exponents corollary, itself only valid because exponents are uniquely defined. A

\[ \gcd(2520,3300) = 60, \qquad \mathrm{lcm}(2520,3300) = 2^3\cdot3^2\cdot5^2\cdot7\cdot11 = 138600 \]

Reading. Comparing prime signatures term by term correctly computes gcd/lcm, and the answer does not depend on which factorisation route was taken to find the exponents.

Prove \( \sqrt{2} \) is irrational using FTA.

Setup: suppose for contradiction \( \sqrt{2} = a/b \) with \( a,b \in \mathbb{Z}_{\gt 0} \). A

\[ 2 = \frac{a^2}{b^2} \implies a^2 = 2b^2 \]

Clearing denominators; valid manipulation in \( \mathbb{Z} \). A

By FTA, \( a^2 \) has a well-defined exponent \( v_2(a^2) = 2v_2(a) \), an even number, regardless of how \( a \) is factored. Likewise \( v_2(2b^2) = 1 + 2v_2(b) \), an odd number.

Uses uniqueness of the prime factorisation of \( a \) and of \( b \) to make \( v_2 \) well-defined, then the multiplicativity of \( v_p \) under products (immediate from uniqueness: multiply the two unique factorisations and combine exponents of like primes). B

But \( a^2 = 2b^2 \) is a single integer, and by uniqueness (Steps 7–11) it has exactly one value of \( v_2 \) — it cannot be simultaneously even (from the left expression) and odd (from the right expression).

Direct application of the uniqueness clause of FTA: two expressions for the same integer must yield the same exponent vector. C

\[ \sqrt{2} \notin \mathbb{Q} \]

Reading. No integer can be "half-a-power-of-2" in two incompatible ways at once; FTA is precisely the fact that rules this out, turning a seemingly analytic irrationality question into pure counting of prime exponents.

Problems

Factorise \( 1155 \) into primes and state its exponent vector over the primes \( (2,3,5,7,11)\).
Solution
\( 1155 = 3 \cdot 5 \cdot 7 \cdot 11 \) (check: \( 3\cdot5=15 \), \( 15\cdot7=105 \), \( 105\cdot11=1155 \)). All four factors are prime, so this is complete. Exponent vector over \( (2,3,5,7,11) \): \( (0,1,1,1,1) \).
Use FTA to explain why \( d(n) \), the number of positive divisors of \( n = \prod p_i^{e_i} \), equals \( \prod_i (e_i+1) \).
Solution
By FTA every divisor \( m \) of \( n \) has, by the same uniqueness argument, a factorisation using only the primes \( p_i \) appearing in \( n \) (any other prime factor of \( m \) would force that prime to divide \( n \), contradicting \( n \)'s unique — and fixed — prime list), with exponents \( 0 \leq f_i \leq e_i \) (if some \( f_i \gt e_i \) then \( m \nmid n\) since \( n/m \) would need a negative power of \( p_i \)). Conversely every such choice of exponents gives a distinct divisor by uniqueness. There are \( e_i+1 \) choices for \( f_i\) (namely \( 0,1,\dots,e_i \)) independently for each \( i \), giving \( \prod_i(e_i+1) \) divisors total.
Show that if \( p \) is prime and \( p \mid n^2 \) for an integer \( n \), then \( p \mid n \). Which step of the FTA proof does this reuse directly?
Solution
\( n^2 = n \cdot n \), so \( p \mid n\cdot n \). By Euclid's Lemma (Step 5, the case \( a=b=n \)), \( p \mid n \) or \( p \mid n \) — either way \( p \mid n \). This reuses Step 5 verbatim with \( a=b=n \); it is the general engine behind the \( \sqrt{2} \) argument in Worked Example 2, generalised from \( p=2 \) to any prime.
In \( \mathbb{Z}[\sqrt{-5}] \), verify directly that \( 2 \) is irreducible (hint: use the norm \( N(a+b\sqrt{-5})=a^2+5b^2 \), which is multiplicative: \( N(zw)=N(z)N(w)\)), and explain precisely which step of the FTA uniqueness proof this blocks.
Solution
Suppose \( 2 = zw \) with \( z,w \) non-units. Then \( N(2)=4=N(z)N(w) \). Since \( N \) is multiplicative and \( N(a+b\sqrt{-5})=a^2+5b^2 \geq 0 \) takes only values in \( \{0,1,4,5,6,9,\dots\}\) hitting no value strictly between 1 and 4, the only factorisation of \( 4 \) as a product of two norms \( \gt 1 \) is \( 4=4\cdot1\) or \(1\cdot4\), i.e. one of \(z,w\) has norm 1 and so is a unit — contradiction. Hence \( 2 \) is irreducible. But Fails-without item 1 shows \( 2 \mid (1+\sqrt{-5})(1-\sqrt{-5}) \) while \( 2 \) divides neither factor, so \( 2 \) is irreducible yet not prime. This blocks exactly Step 5 (Euclid's Lemma) of the proof, which is where irreducibility of \( q_1 \) was upgraded to "\( p_1 \mid q_1 \Rightarrow p_1=q_1 \)"; without the prime property that upgrade is unavailable, so Steps 8–11 cannot proceed.
A student claims: "FTA shows every integer \( \gt 1 \) has a divisor that is prime." Is this claim actually equivalent to FTA, weaker, or does it need a separate (easier) argument? Justify.
Solution
It is strictly weaker than FTA, and needs only the existence half (Steps 1–3), not uniqueness. Directly: let \( n \gt 1 \) and let \( p \) be the smallest divisor of \( n \) that is \( \gt 1 \) (exists by well-ordering, since the set of divisors of \( n \) exceeding 1 is nonempty as it contains \( n \) itself). If \( p \) were composite, \( p=ab \) with \( 1\lt a \lt p\), and \( a \mid p \mid n \) so \( a\) would be a divisor of \( n \) with \( 1 \lt a \lt p \), contradicting minimality of \( p \); hence \( p \) is prime. This is a much shorter argument than the full proof of FTA and does not touch Bézout, Euclid's Lemma, or uniqueness at all — it only needs well-ordering, so the claim is a genuine sub-result, not equivalent to the full theorem.