Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic, also called the unique factorization theorem, consists of two main assertions for any integer [latex]n > 1[/latex]: first, that [latex]n[/latex] can be written as a product of prime numbers (the existence part), and second, that this product is unique, apart from the order of the factors (the uniqueness part). The existence of a prime factorization is typically proven using strong induction. The base case is that 2 is prime. For the inductive step, assume every integer up to [latex]k[/latex] has a prime factorization. For [latex]k+1[/latex], it is either prime (and we are done) or composite. If it is composite, it can be written as a product of two smaller integers, [latex]a \times b[/latex]. By the induction hypothesis, both [latex]a[/latex] and [latex]b[/latex] have prime factorizations, and their product gives a prime factorization for [latex]k+1[/latex].

The uniqueness part is more subtle and relies critically on Euclid’s Lemma, which states that if a prime [latex]p[/latex] divides a product [latex]ab[/latex], then [latex]p[/latex] must divide either [latex]a[/latex] or [latex]b[/latex]. To prove uniqueness, assume an integer [latex]n[/latex] has two different prime factorizations: [latex]n = p_1 p_2 cdots p_k = q_1 q_2 cdots q_m[/latex]. The prime [latex]p_1[/latex] divides the left side, so it must divide the right side. By Euclid’s Lemma, [latex]p_1[/latex] must divide one of the [latex]q_j[/latex]. Since all [latex]q_j[/latex] are prime, [latex]p_1[/latex] must be equal to some [latex]q_j[/latex]. We can then cancel these terms from both sides and repeat the process, eventually showing that the two factorizations must be identical. While elements of this theorem appeared in Euclid’s *Elements* (c. 300 BC), Carl Friedrich Gauss provided the first clear statement and rigorous proof in his 1801 work *Disquisitiones Arithmeticae*, solidifying its foundational role in number theory.