2.3: Factoring into Primes

Last updated
Save as PDF

Page ID: 48302

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

We’ve previously taken for granted the Prime Factorization Theorem, also known as the Unique Factorization Theorem and the Fundamental Theorem of Arithmetic, which states that every integer greater than one has a unique¹ expression as a product of prime numbers. This is another of those familiar mathematical facts which are taken for granted but are not really obvious on closer inspection. We’ll prove the uniqueness of prime factorization in a later chapter, but well ordering gives an easy proof that every integer greater than one can be expressed as some product of primes.

Theorem \(\PageIndex{1}\)

Every positive integer greater than one can be factored as a product of primes.

Proof

The proof is by well ordering.

Let \(C\) be the set of all integers greater than one that cannot be factored as a product of primes. We assume \(C\) is not empty and derive a contradiction.

If \(C\) is not empty, there is a least element, \(n \in C\), by well ordering. The \(n\) can’t be prime, because a prime by itself is considered a (length one) product of primes and no such products are in \(C\).

So \(n\) must be a product of two integers \(a\) and \(b\) where \(1 < a, b < n\). Since \(a\) and \(b\) are smaller than the smallest element in \(C\), we know that \(a, b \notin C\). In other words, \(a\) can be written as a product of primes \(p_1 p_2 \cdots p_k\) and \(b\) as a product of primes \(q_1 \cdots q_l\). Therefore, \(n = p_1 \cdots p_k q_1 \cdots q_l\) can be written as a product of primes, contradicting the claim that \(n \in C\). Our assumption that \(C\) is not empty must therefore be false. \(\quad \blacksquare\)

¹. . . unique up to the order in which the prime factors appear