Prime Decomposition of Integer is Unique

From ProofWiki
Jump to: navigation, search

Theorem

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


Then the prime decomposition of $n$ is unique.


Proof

From Integer is Expressible as Product of Primes, $n$ can be expressed as the product of one or more primes.

Let $n = q_1 q_2 \dotsm q_s$ where $q_1, q_2, \ldots, q_s$ are all primes such that:

$(1): \quad n = q_1 \le q_2 \le \dotsb \le q_s$

From Expression for Integer as Product of Primes is Unique, the expression for $(1)$ is unique.


By the Fundamental Theorem of Equivalence Relations, we can partition $\set {q_1, q_2, \dotsc, q_s}$ in $(1)$ according to equality.

Thus the equivalence classes $\eqclass {q_j} =$ contain all repetitions of $q_j$.

Hence the contribution of $q_j$ to $n$ is:

${q_j}^{k_j}$

where $k_j = \card {\eqclass {q_j} =}$, the cardinality of $\eqclass {q_j} =$.

Renaming the representative elements of the various $\eqclass {q_r} =$ as $p_1, p_2, \ldots, p_r$, where $r$ is the number of equivalence classes.

Hence:

$n = {p_1}^{k_1} {p_2}^{k_2} \dotsm {p_r}^{k^r}$


As $n = q_1 \le q_2 \le \dotsb \le q_s$ is a unique representation, so is $n = {p_1}^{k_1} {p_2}^{k_2} \dotsm {p_r}^{k^r}$.

$\blacksquare$


Sources