State/Uniqueness of prime factorization

From SlugmathWiki

Theorem
Proof

Theorem: (Uniqueness of prime factorization) Suppose that $n$ is a natural number, and $n \geq 1$. Suppose that $p_1, \ldots, p_k$ and $q_1, \ldots, q_\ell$ are two finite sequences of prime numbers, and: $$n = \prod_{i=1}^k p_i = \prod_{j=1}^\ell q_j.$$ Then the following two statements hold:

$k = \ell$.
There exists a permutation $\sigma$ of $\{ 1, \ldots, k \}$, such that:

$$\forall i \in \{1, \ldots, k \}, p_i = q_{\sigma(i)}.$$

Logical Connections

This statement logically relies on the following definitions and statements: Def/Finite sequence, Def/Prime number, Def/Permutation, State/Multiplication increases size, State/Primes dividing a product must divide a factor, Def/Transposition, Def/Fixed point

The following statements and definitions rely on the material of this page: Def/Canonical decomposition into primes, and State/Computing the totient of a prime power

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

We prove the result by induction on $k$ (the length of the sequence $p_1, \ldots, p_k$:

$k=0$

If $k = 0$, then $n = 1$, the empty product. It follows that $\prod_{j=1}^\ell q_j = 1$. Since multiplication increasese the size of natural numbers, this is impossible unless $\ell = 0$, i.e., unless this is the empty product as well. Hence $k = \ell$. The two empty sequences are equal (using the trivial permutation of $\emptyset$).

$k > 0$.

Suppose that $k > 0$, and the result has been proven for all smaller values of $k$. Recall that we have two factorizations of $n$ into prime numbers:

$$n = p_1 \cdots p_k = q_1 \cdots q_\ell.$$ Since $k > 0$, we may define $n' = p_1 \cdots p_{k-1}$, so that $n = n' \cdot p_k$. Since $p_k$ divides $n$, we find that $p_k$ divides $q_1 \cdots q_\ell$. In particular, $\ell > 0$, since $p_k$ does not divide $1$. Recall that primes dividing a product must divide a factor. Therefore, there exists $j \in \{1, \ldots, \ell \}$ such that $p_k$ divides $q_j$.

Since $p_k \neq 1$, it follows from the primality of $q_j$ that $p_k = q_j$. Let $\tau$ be the permutation of $\{1, \ldots, \ell \}$ which transposes $j$ and $\ell$. Thus, $q_{\tau(\ell)} = p_k$. By cancellation of $p_k$, we find that: $$n' = p_1 \cdots p_{k-1} = q_{\tau(1)} \cdots q_{\tau(\ell - 1)}.$$ By the inductive hypothesis, this implies two statements:

$k-1 = \ell - 1$.
There exists a permutation $\sigma'$ of $\{1, \ldots, k-1 \}$, such that $p_i = q_{\tau(\sigma'(i)))}$ for all $i \in \{1, \ldots, k-1 \}$.

From the first of these statements, we find that $k = \ell$. Consider the permutation $\sigma = \tau \circ \tilde \sigma'$, where $\tilde \sigma'$ is the unique permutation of $\{1, \ldots, k \}$ which extends $\sigma'$ and fixes $k$. From the second of the above statements, we find that $p_i = q_{\sigma(i)}$ for all $i \in \{1, \ldots, k-1 \}$. Furthermore, we find that: $$q_{\sigma(k)} = q_{\tau(\tilde \sigma'(k))} = q_{\tau(k)} = q_j = p_k.$$ Therefore, for all $i \in \{1, \ldots, k \}$, we find that $q_{\sigma(i)} = p_i$.

Hence the factorization of $n$ into primes is unique, up to permutation.

State/Uniqueness of prime factorization

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox