_Posted on April 16, 2024_ ##### Introduction Statement of the fundamental theorem of arithmetic: > [!theorem] **Fundamental Theorem of Arithmetic:** _Every integer $n$ with $|n| \gt 1$ can be expressed as a product of finitely many prime numbers, up to the order of the factors._ In this post, I divide the proof into two parts. First proving the existence of the prime factorizations, then proving that the factorizations are unique. I do this since typically the uniqueness proof relies on [[Euclid's Lemma]], but I provide 2 uniqueness proofs. One that does not assume Euclid's Lemma, and one that does. ##### Proof ###### Existence In this proof, we only consider $n > 1$, since we can incorporate signs into the factors. First, we show that any $n$ can be expressed as a product of prime numbers. For the sake of contradiction, suppose that the set $S$ of integers greater than $1$ which are _not_ expressible as a product of prime numbers is nonempty. By the [[Euclid's Division Lemma#^ee5ece|well ordering principle]], $S$ contains a least element $n$. Note that $n$ cannot be prime. Thus, by the definition of prime, $n$ must be divisible by some integer $a \neq n,1$. Thus, $ab = n$ for integers $a$ and $b$. We can assume $a$ and $b$ are positive, since $n$ is positive. By [[Euclid's Division Lemma#^40f373|the divisor magnitude lemma]], $1 < a < n$ and $1 < b < n$. Since $a$ and $b$ are less than $n$, they are not in $S$. Thus, $a$ and $b$ do have prime factorizations $a=p_1...p_u$ and $b=p'_1...p'_v$. But since $n = ab$, $n$ is expressible as the product of primes $p_1...p_up'_1...p'_v$. Thus, $n \notin S$, a contradiction. We have now shown that every integer is expressible as a product of primes $\blacksquare$. ###### Uniqueness Without Euclid's Lemma: Suppose that $S_1$ is the set of integers whose prime factorizations are not unique. $S_1$ has a least element $n$ by the [[Euclid's Division Lemma#^ee5ece|well ordering principle]]. Let $n = q_1...q_u$= $q'_1...q'_v$ be two distinct prime factorizations of $n$. Suppose that some $q_i = q'_j$. Then, we can reorder the factorizations so that $i=j=1$, and then we have $q_2...q_u = q'_2...q'_v =\displaystyle \frac{n}{q_1}< n$, which are thus not in $S_1$ and so do not have _unique_ factorizations. Thus, $u = v$ and $q_i = q'_i$ for all $0 < i < v$. Thus, the factorizations of $n$ are not unique and $n \notin S_1$. Now suppose that there are no $q_i$ and $q'_j$ such that $q_i = q'_j$. Without loss of generality, suppose that $q_1 < q'_1$. Let $Q = q_2...q_u$ and $Q'=q'_2...q'_v$. Since $q_1 < q'_1$, $Q' < Q$ and it follows that $n-q_1Q'=(q'_1-q_1)Q'=q_1(Q-Q') < n$. Since $(q'_1-q_1)Q' < n$ it has a unique factorization, and so $q_1$ must be in the factorization of $Q'$ or $q'_1 - q_1$. However, $q_1$ cannot be in the factorization of $Q'$ because $p_1$ differs from every $q_j$, as established above. Additionally, $q_1$ cannot be in the factorization of $q'_1 - q_1$ because $q_1k = q'_1 - q_1 \implies q_1(k + 1) = q'_1 \implies q_1 \mid q'_1$, which is impossible, because $q_1$ and $q'_1$ are distinct prime $\blacksquare$. With Euclid's Lemma: Suppose that $S_1$ is the set of integers who's prime factorizations are not unique. $S_1$ has a least element $n$ by the [[Euclid's Division Lemma#^ee5ece|well ordering principle]]. Let $n = q_1...q_u=q'_1...q'_v$ be two distinct prime factorizations of $n$. Thus, $q_1 \mid q'_1...q'_v$. By [[Euclid's Lemma]], $q_q \mid q'_j$ for some $0<j<v$. We can reorder the terms so that $j = 1$. However, since $q_1$ and $q'_1$ are prime, $q_1 = q'_1$ by the definition of prime. Thus, we have $q_2...q_u = q'_2...q'_v =\displaystyle \frac{n}{q_1} < n$, so $q_2...q_u = q'_2...q'_v \notin S_1$ and so have unique prime factorizations. Thus $u = v$ and $q_i = q'_i$ for all $0 < i < u$ $\blacksquare$.