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.
 A: 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<p_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<p_1.$ 
We have $$0<X\le sX=(p_1-kq_1)X=p_1X-kq_1X=$$ $$=P-kq_1X=$$ $$=q_1Y-kq_1X=q_1(Y-kX).$$ $(2).$ So we have $0<sX=q_1(Y-k X).$ 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<q_1.$
$(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<p_1X=P=\min E.$
A: 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$?
A: 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.
A: 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. :)
A: 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).
