Vtgyjfy

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.

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$?

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 < nRightarrow n in X) Rightarrow (X = mathbb{N})$

Now, let

$X = {xin 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 < nRightarrow 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. :)