Fundamental Theorem of Arithmetic

From AoPSWiki

The Fundamental Theorem of Arithmetic states that every positive integer $n$ can be written as a product $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$ where the $p_i$ are all prime numbers; moreover, this expression for $n$ (called its prime factorization) is unique, up to rearrangement of the factors.

Note that the property of uniqueness is not, in general, true for other sorts of factorizations. For example, most integers have many factorizations into 2 parts: $30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$ . Thus, the Fundamental Theorem of Arithmetic tells us in some sense that "factorizations into prime numbers is deeper than factorization into two parts."

Proofs

The most common elementary proof of the theorem involves induction and use of Euclid's Lemma, which states that if $a$ and $b$ are natural numbers and $p$ is a prime number such that $p \mid ab$ , then $p \mid a$ or $p \mid b$ . This proof is not terribly interesting, but it does prove that every Euclidean domain has unique prime factorization.