Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every positive integer can be written as a product where the are all prime numbers; moreover, this expression for (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: . Thus, the Fundamental Theorem of Arithmetic tells us in some sense that "factorizations into prime numbers is deeper than factorization into two parts."

Proof

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

The proof below uses group theory, specifically the Jordan-Hölder Theorem.

Proof by Group Theory

Suppose that , for primes and . Then both of the composition series are Jordan-Hölder series, and their quotients are and Then by the Jordan-Hölder Theorem, the primes are a rearrangement of the primes . Therefore the prime factorization of is unique.

This article is a stub. Help us out by expanding it.