# Proof - Uniqueness part of unique factorization theorem

The uniqueness part of the unique factorization theorem for integers says that given any integer $n$, if $n=p_1p_2 \ldots p_r=q_1q_2 \ldots q_s$ for some positive integers $r$ and $s$ and prime numbers $p_1 \leq p_2 \leq \cdots \leq p_r$ and $q_1 \leq q_2 \leq \cdots \leq q_s$, then $r=s$ and $p_i=q_i$ for all integers $i$ with $1 \leq i \leq r$.

Fill in the details of the following sketch of a proof: Suppose that $n$ is an integer with two different prime factorizations: $n=p_1p_2 \ldots p_t =q_1q_2 \ldots q_u$. All the prime factors that appear on both sides can be cancelled (as many times as they appear on both sides) to arrive at the situation where $p_1p_2 \ldots p_r=q_1q_2 \ldots q_s$, $p_1 \leq p_2 \leq \cdots \leq p_r$, $q_1 \leq q_2 \leq \cdots \leq q_s$ , and $p_i \neq q_j$ for any integers $i$ and $j$. Then deduce a contradiction, and so the prime factorization of $n$ is unique except, possibly, for the order in which the prime factors are written.

Please provide as much detail as possible. I'm very confused about this. I know I'll need Euclid's Lemma at some point in the contradiction, but I have no idea how to arrive there.

• what are you confused with? Sep 2, 2015 at 17:51

Without Euclid's Lemma or Bezout's Identity & all that.

Preface. We consider "$$1$$" to be the unique prime factorization of $$1$$, so as to not need to discuss some special cases separately.

By contradiction, suppose $$\emptyset \ne E= \{A\in \Bbb N : A \text { has more than one prime factorization }\}.$$ Let $$P =\min E.$$ Then for some unequal increasing finite sequences $$(p_1,...,p_m)$$ and $$(q_1,...,q_n)$$ of primes we have $$(1)...\quad P=\prod_{i=1}^mp_i=\prod_{j=1}^nq_j.$$

We have $$m\ge 2$$ and $$n\ge 2,$$ otherwise the prime $$p_1=P$$ is divisible by some prime $$q_j\ne p_1,$$ or the prime $$q_1=P$$ is divisible by some prime $$p_i\ne q_1.$$

Now if any $$p_i=q_j=r$$ for any $$i,j$$ then we could divide $$(1)$$ by $$r$$ and get $$\min E=P>P/r\in E,$$ which is absurd. So no $$p_i$$ equals any $$q_j.$$

Let $$\prod_{i=2}^mp_i=X$$ and $$\prod_{j=2}^n q_j=Y.$$ So we can write $$P=p_1X=q_1Y.$$ WLOG (without loss of generality) let $$q_1 There exists a (unique) $$k\in \Bbb N$$ such that $$kq_1\le p_1<(k+1)q_1.$$ Let $$s=p_1-kq_1.$$ We have $$s\ne 0$$ otherwise the prime $$p_1$$ would be divisible by the smaller prime $$q_1$$.

So $$1\le s=p_1-kq_1<(k+1)q_1-kq_1=q_1

We have $$0 $$=P-kq_1X=$$ $$=q_1Y-kq_1X=q_1(Y-kX).$$ $$(2).$$ So we have $$0 This also implies $$Y-kX\ge 1.$$

Now $$X$$ has a prime factorization that does not include $$q_1$$ and no prime factorization of $$s$$ can include $$q_1$$ because $$s

$$(3).$$ So $$sX$$ has a prime factorization that $$does$$ $$not$$ include $$q_1.$$

$$(4).$$ And $$q_1$$ times any prime factorization of $$(Y-kX)$$ is a prime factorization of $$q_1(Y -kX)$$ that $$does$$ include $$q_1.$$

But $$(2).sX=q_1(Y-kX).$$ So by $$(3)$$ and $$(4)$$ we have $$sX\in E.$$ This is absurd because $$sX

• The logic: $\quad \text { has more than one prime factorization }\quad$ leaves finding a smaller 'minimal criminal' more 'loose' than the brute force elementary method given by Zermelo. (+1) Jul 23, 2019 at 0:17
• @CopyPasteIt. I'm sure I once saw a much briefer version of this but I think it may have used the result ( somehow ) that if $a|bc$ and $\gcd(a,b)=1$ then $a|c.$ Jul 24, 2019 at 11:37

You want a contradiction that shows $p_1...p_r \neq q_1...q_s$. Is it possible for $p_1$ to divide $q_1...q_s$ or $p_1...p_s$?

• This is actually a pretty good response, but someone flagged it as a "low quality post." My guess is because it technically isn't an "answer," however constructive it actually might be. I'll opt for "skip" in the review queue instead of "recommend deletion." Sep 2, 2015 at 18:12

From $p_1p_2 \ldots p_r=q_1q_2 \ldots q_s$ we deduce that $p_r$ divides $q_1q_2 \ldots q_s$. Since $p_r$ is a prime and $q_1q_2 \ldots q_s$ a product , we can apply Euclid's lemma and conclude that $p_r$ must divide one of the $q_i$.

But this cannot be true, since $q_i$ is prime and $p_r \neq q_i$. This is our desired contradiction.

The contradiction can be obtained following this way:

Suppose that there exists a number (natural number) with two different prime factorizations: Now, consider that n is the smallest of all natural number with that condition.

$$n' = p_{1}. p_{2}. p_{3}... p_{t} = q_{1}. q_{2}. q_{3}... q_{u}...(1)$$

Being The Second Principle of Induction:

Let $$X \subseteq \mathbb{N}$$. Given $$n (\geq 2) \in \mathbb{N}: (m \in X, \forall m < n\Rightarrow n \in X) \Rightarrow (X = \mathbb{N})$$

Now, let

$$X = \{x\in \mathbb{N}: x = 1 \vee x = x_{1}. x_{2}. x_{3}... x_{r} = y_{1}. y_{2}. y_{3}... y_{s}; x_{i}, y_{j}\in \mathbb{N} ($$prime numbers$$)\Rightarrow r = s; x_{1} = y_{1}, x_{2} = y_{2}, x_{3} = y_{3},..., x_{r} = y_{s}\}\Rightarrow X \neq \mathbb{N}$$

$$\Rightarrow \thicksim (m \in X, \forall m < n\Rightarrow n \in X)$$ (by the contrapositive of The Second Principle of Induction).

$$\Rightarrow m \in X, \forall m < n \wedge n \notin X$$ (Watch out! n is an arbitrary number greater than 1 with the condition that doesn't belong to X).

$$\Rightarrow n' \notin X$$

Let $$n'' = p_{1}. p_{2}. p_{3}... p_{t}.p_{t+1} = q_{1}. q_{2}. q_{3}... q_{u}.p_{t+1} \Rightarrow n' < n''$$ ($$p_{t+1}$$ is a prime number).

$$\Rightarrow n'' \notin X \Rightarrow m \in X, \forall m < n''$$

$$\Rightarrow n' \in X$$ (absurd!).

Sorry for my English. :)

The OP can simply state in their proof that they 'arrived' at the following 'situation':

$$\tag 1 n = p_1p_2 \ldots p_r \text{ and } n=q_1q_2 \ldots q_s \text{ and } p_i \neq q_j \text { for any integers } i \text{ and } j$$

In words, there exist an integer $$n$$ with two prime factorizations containing no common prime factors.

We now demonstrate that being left in such a 'situation' is untenable by using the following 'tweak' of Euclid's lemma:

If $$p$$ is a prime number dividing into $$a_1 \dots a_z$$ then there exist a subscript $$k$$ such that $$p$$ divides $$a_k$$.

The integer $$n$$ in $$\text{(1)}$$ has a smallest prime number, call it $$\gamma(n)$$, that divides into it. By applying Euclid's lemma to $$n = p_1p_2 \ldots p_r$$, we must conclude that there exist a subscript $$i$$ with $$\gamma(n) = p_i$$. Similarly, there exist a subscript $$j$$ with $$\gamma(n) = q_j$$. But this contradicts $$\text{(1)}$$.

The above proof is similar to Falko's, but since it has more detail and introduces the concept of $$\gamma(n)$$, I decided to post it. (I just upvoted Falko's answer).