0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what are you confused with? $\endgroup$ – RowanS Sep 2 '15 at 17:51
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – daOnlyBG Sep 2 '15 at 18:12
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.