Fundamental Theorem of Arithmetic

Theorem

For every integer $n$ such that $n > 1$, $n$ can be expressed as the product of one or more primes, uniquely up to the order in which they appear.

Proof 1

Proof of Existence

If $n$ is prime, the result is immediate.

Let $n$ be composite.

Then by Composite Number has Two Divisors Less Than It, $\exists r, s \in \Z: n = r s, 1 < r < n, 1 < s < n$.

This being the case, the set $S_1 = \{d: d \backslash n, 1 < d < n\}$ is nonempty, and bounded below by $1$.

By Integers Bounded Below has Smallest Element, $S_1$ has a smallest element, which we will call $p_1$.

If $p_1$ is composite, then by Composite Number has Two Divisors Less Than It, it has at least two divisors $a, b$, such that $a, b \backslash p_1$ and $1 < a < p_1, 1 < b < p_1$.

But by Divides is Ordering on Positive Integers, it follows that $a, b \backslash n$ and hence $a, b \in S$, which contradicts the assertion that $p_1$ is the smallest element of $S_1$.

Thus, $p_1$ is necessarily prime.

We may now write $n = p_1 n_1$, where $n > n_1 > 1$.

If $n_1$ is prime, we are done.

Otherwise, the set $S_2 = \{d: d \backslash n_1, 1 < d < n_1\}$ is nonempty, and bounded below by $1$.

By the above argument, the smallest element $p_2$ of $S_2$ is prime.

Thus we may write $n_1 = p_2 n_2$, where $1 < n_2 < n_1$.

This gives us $ n = p_1 p_2 n_2$.

If $n_2$ is prime, we are done.

Otherwise, we continue this process.

Since $ n > n_1 > n_2 > \ldots > 1$ is a decreasing sequence of positive integers, there must be a finite number of $n_i$'s.

That is, we will arrive at some prime number $n_{k-1}$, which we will call $p_k$.

This results in the prime factorization $n = p_1 p_2 \cdots p_k$.

$\Box$

Proof of Uniqueness

Now, suppose $n$ has two prime factorizations, namely $n = p_1 p_2 \dots p_r = q_1 q_2 \dots q_s$, where $r \le s$ and each $p_i$ and $q_j$ is prime with $p_1 \le p_2 \le \dots \le p_r$ and $q_1 \le q_2 \le \dots \le q_s$.

Since $p_1 \backslash q_1 q_2 \dots q_s$, it follows from Euclid's Lemma for Prime Divisors that $p_1 = q_j,$ for some $1 \le j \le s$.

This means $p_1 \ge q_1$.

Similarly, since $q_1 \backslash p_1 p_2 \dots p_r$, from Euclid's Lemma for Prime Divisors we have $q_1 \ge p_1$.

Thus, $p_1 = q_1$, so we may cancel these common factors, which gives us $p_2 p_3 \cdots p_r = q_2 q_3 \dots q_s$.

We may repeat this process to show that $p_2 = q_2, p_3 = q_3, \ldots, p_r = q_r$.

If $r < s$, we arrive at $1 = q_{r+1} q_{r+2} \cdots q_s$ after canceling all common factors.

Of course, this is impossible, which means $r = s$.

Thus, $p_1 = q_1, p_2 = q_2, \ldots, p_r = q_s$, which means the two factorizations are identical.

Therefore, the prime factorization of $n$ is unique.

$\blacksquare$

Proof 2

Proof of Existence

Suppose this supposition is false. Let $m$ be the smallest number which can not be expressed as the product of primes.

As a prime number is trivially a product of primes, $m$ can not itself be prime.

Hence $\exists r, s \in \Z: 1 < r < m, 1 < s < m: m = r s$.

As $m$ is our least counterexample, both $r$ and $s$ can be expressed as the product of primes.

Say $r = p_1 p_2 \cdots p_k$ and $s = q_1 q_2 \cdots q_l$, where all of $p_1, \ldots, p_k, q_1, \ldots, q_l$ are prime.

Hence $m = r s = p_1 p_2 \cdots p_k q_1 q_2 \cdots q_l$, which is a product of primes.

Hence there is no such counterexample.

Proof of Uniqueness

Suppose the supposition false, that is, there is at least one number that can be expressed in more than one way as a product of primes. Let the least of these be $m$.

That is, $m$ is the smallest number which can be expressed in at least two ways, that is: $m = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$, where all of $p_1, \ldots p_r, q_1, \ldots q_s$ are prime.

Clearly $m$ can not be prime, therefore $r, s \ge 2$.

Let us arrange that the primes are in order of size, that is, $p_1 \le p_2 \le \dots \le p_r$ and $q_1 \le q_2 \le \dots \le q_s$, and also let us arrange that $p_1 \le q_1$.

Now suppose $p_1 = q_1$. Then:

$\displaystyle \frac m {p_1} = p_2 p_3 \cdots p_r = q_2 q_3 \cdots q_s = \frac m {q_1}$

But then we have the integer $\displaystyle \frac m {p_1}$ being expressible in two different ways, thus contradicting the fact that $m$ is the smallest number that can be so expressed.

Therefore, $p_1 \ne q_1 \implies p_1 < q_1 \implies p_1 < q_2, q_3, \ldots, q_s$ as we arranged them in order.

Now: $1 < p_1 < q_j: 1 < j < s \implies p_1 \nmid q_j$ from Prime Not Divisor then Coprime.

But $p_1 \backslash m \implies p_1 \backslash q_1 q_2 \ldots q_s$.

Thus $\exists j: 1 \le j \le s: p_1 \backslash q_j$ from Euclid's Lemma for Prime Divisors.

But $q_j$ was supposed to be a prime.

This gives us our contradiction, and there is therefore no such counterexample to our supposition.

$\blacksquare$

Also known as

This result is otherwise known as the unique factorization theorem.

However, this is the name of the equivalent result for the general Euclidean domain and it can be argued that the names are best kept separate.

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Exercise $21$
• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.13$: Theorem $22$
• George E. Andrews: Number Theory (1971): $\S 2.4$: Theorem $2.5$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 24$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 13$
• George F. Simmons: Calculus Gems (1992): Chapter $\text{B}.2, \ \text{B}.16$ Theorem $1$