# 2.3: Factoring into Primes

• 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}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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 unique1 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$$

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

This page titled 2.3: Factoring into Primes is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .