TheoremProved

Fundamental theorem of arithmetic

Statement

Every integer $n>1$ can be written as a product of primes, $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ , and this factorization is unique up to the order of the factors.

Why is it true?

Primes are the indivisible 'atoms' of multiplication. Existence follows by repeatedly splitting off a smallest prime factor; uniqueness follows because a prime dividing a product must divide one of the factors (Euclid's lemma), which rules out two genuinely different factorizations of the same number.

Proof sketch

Existence: strong induction on $n$ — every $n>1$ is either prime, or a product of two smaller integers $>1$ , each of which factors into primes by the induction hypothesis. Uniqueness: from Euclid's lemma ( $p\mid ab\Rightarrow p\mid a$ or $p\mid b$ , itself derived from Bézout's identity), repeatedly cancel matching primes from two supposed factorizations of the same $n$ until both sides are exhausted, forcing them to agree.

Stated by

stated -300Euclid of Alexandria

Proved by

proved 1801Carl Friedrich Gauss

Topics that use this theorem

Prime numbers Divisibility, factors and multiples The Riemann zeta function and the Riemann hypothesis

Related theorems

Infinitude of primes (Euclid)Bézout's identity

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Carl Friedrich Gauss (trans. Arthur A. Clarke) (1986). Disquisitiones Arithmeticae
G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001