# 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? – RowanS Sep 2 '15 at 17:51

## 5 Answers

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.

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) – CopyPasteIt Jul 23 '19 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.$ – DanielWainfleet Jul 24 '19 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." – daOnlyBG Sep 2 '15 at 18:12

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