# Prime Decomposition of Integer is Unique

## Theorem

Let $n$ be an integer such that $n > 1$.

Then the expression for $n$ as the product of one or more primes is unique up to the order in which they appear.

In the words of Euclid:

*If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.*

(*The Elements*: Book $\text{IX}$: Proposition $14$)

## Proof 1

Aiming for a contradiction, suppose the supposition false.

That is, suppose there is at least one positive integer that can be expressed in more than one way as a product of primes.

Let the smallest of these be $m$.

Thus:

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

By definition, $m$ is not itself prime.

Therefore:

- $r, s \ge 2$

Let us arrange that the primes which compose $m$ are in order of size:

- $p_1 \le p_2 \le \dots \le p_r$

and:

- $q_1 \le q_2 \le \dots \le q_s$

Let us arrange that $p_1 \le q_1$.

Suppose $p_1 = q_1$.

Then:

- $\dfrac m {p_1} = p_2 p_3 \cdots p_r = q_2 q_3 \cdots q_s = \dfrac m {q_1}$

But then we have the positive integer $\dfrac m {p_1}$ being expressible in two different ways.

This contradicts the fact that $m$ is the smallest positive integer 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.

From Prime not Divisor implies Coprime:

- $1 < p_1 < q_j: 1 < j < s \implies p_1 \nmid q_j$

But:

- $p_1 \divides m \implies p_1 \divides q_1 q_2 \ldots q_s$

where $\divides$ denotes divisibility.

Thus from Euclid's Lemma for Prime Divisors:

- $\exists j: 1 \le j \le s: p_1 \divides q_j$

But $q_j$ was supposed to be a prime.

This is a contradiction.

Hence, by Proof by Contradiction, the supposition was false.

$\blacksquare$

## Proof 2

Suppose $n$ has two prime factorizations:

- $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 \mathrel \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$.

Thus:

- $p_1 \ge q_1$

Similarly, since $q_1 \mathrel \backslash p_1 p_2 \dots p_r$, from Euclid's Lemma for Prime Divisors:

- $q_1 \ge p_1$

Thus, $p_1 = q_1$, so we may cancel these common factors, which gives:

- $p_2 p_3 \cdots p_r = q_2 q_3 \dots q_s$

This process is repeated 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.

But by Divisors of One, the only divisors $1$ are $1$ and $-1$.

Hence $q_{r+1}, q_{r+2}, \ldots, q_s$ cannot be prime numbers

From that contradiction it follows that $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 factorizations of $n$ is unique.

$\blacksquare$

## Also see

## Historical Note

This theorem is Proposition $14$ of Book $\text{IX}$ of Euclid's *The Elements*.

## Sources

- 1926: Sir Thomas L. Heath:
*Euclid: The Thirteen Books of The Elements: Volume 2*(2nd ed.) ... (previous) ... (next): Book $\text{IX}$. Propositions - 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {B}.16$: The Sequence of Primes: Problem $1 \ \text{(b)}$ - 2008: Ian Stewart:
*Taming the Infinite*... (previous) ... (next): Chapter $7$: Patterns in Numbers