4
$\begingroup$

Help! Can you please see if there are any errors in this proof by contradiction that I wrote? Assume that there exists a positive integer n with a prime factorization that is not unique up to the ordering of its prime factors. This means there must at least two different prime factorizations for n.

Let $n = p_1 \cdot p_2 \cdots p_m = q_1 \cdot q_2 \cdots q_k$, where each $p_i$ and $q_j$ are positive prime numbers and each $p_i \neq q_j.$ Without loss of generality, assume that $p_1 \leq p_i$ and that $p_1 < q_j.$ Since $p_1$ is a factor of $n$, $p_1 \mid n.$ However, since $p_i \neq q_j$ implies $p_1 \neq q_j,$ it must be that $p_1 \not\mid q_1 \cdot q_2 \cdots q_k,$ otherwise this would contradict that each $q_j$ is prime and has only itself and $1$ as positive factors. By substituting $q_1 \cdot q_2 \cdots q_k$ for $n,$ $p_1 \not\mid n.$

$p_1 \mid n$ and $p_1 \not\mid n$ is a contradiction, which means the original assumption was false. It must follow that every positive integer's prime factorization is unique up to the ordering of its prime factors.

$\endgroup$
4
  • $\begingroup$ And what exactly is the question? $\endgroup$
    – Old John
    Dec 6, 2013 at 21:38
  • $\begingroup$ I wanted to see if there is an error in my proof by contradiction. My Discrete Math textbook had a longer and more complicated proof involving a "minimal criminal" proof by contradiction. I tried to prove this in a simpler and more efficient way. $\endgroup$
    – cebroski
    Dec 6, 2013 at 21:39
  • $\begingroup$ Then it might be better to edit this into the post to make it clear that you are asking a question. $\endgroup$
    – Old John
    Dec 6, 2013 at 21:40
  • 2
    $\begingroup$ The proof implicitly uses the fact that if a prime $p$ divides a product (say of primes, but it doesn't matter) then $p$ divides one of the terms in the product. This (or the product of $2$ terms version) is sometimes called Euclid's Lemma. One has to refer to it, since it is the fundamental non-trivial component of the proof. Failure of Euclid's Lemma is what makes unique facorization fail in many important instances. $\endgroup$ Dec 6, 2013 at 22:12

2 Answers 2

3
$\begingroup$

There is one (rather large) assumption that you make without justification: namely, that $p_i\ne q_j$ for all $i,j.$ It actually is okay to assume that, but it needs justification. In particular, we should assume that $n$ is the least positive integer without a unique factorization. We know that $n$ is composite, and can't have any common primes in its two factorizations, for if so, division by those primes would yield a smaller positive integer with nonunique factorization.

More simply, we could assume by way of contradiction (and without justification) that some $p_i$ is not equal to any of the $q_j$s, or that some $q_j$ is not equal to any of the $p_i$s. Without loss of generality, we can assume that $p_1$ is not equal to any of the $q_j$s. Since $p_1\mid n=q_1\cdots q_k,$ then since $p_1$ is prime, we have that $p_1\mid q_j$ for some $j,$ but this would imply that $p_1=q_j,$ a contradiction.

This uses the fact that the prime integers are precisely those integers $p$ such that if $p\mid a\cdot b$ for some integers $a,b,$ then $p\mid a$ or $p\mid b.$ If you don't know (haven't proved) this fact, then your approach works just fine, with justification.

$\endgroup$
2
  • $\begingroup$ I would rather say that apart from missing the assumption (can I say, axiom) of '$n$ is the least positive integer without a unique factorization', the OP has not stated your (and @Andre's comment) second assumption that if $p\mid a\cdot b$ for some integers $a,b$; then $p \mid a$ or $p\mid b$. $\endgroup$
    – jiten
    Jan 29, 2018 at 16:05
  • 1
    $\begingroup$ That's what my last paragraph addresses. In many courses, prime numbers are defined as those integers greater than $1$ which have the property André and I mentioned. However, it isn't clear whether the OP was familiar with this. $\endgroup$ Jan 29, 2018 at 19:09
0
$\begingroup$

Proof:

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})$

So, keep in mind that our hypothesis is: $m \in X, \forall m < 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}\}$

Let $n \geq 2$

Based on The Prime Factorisation Theorem: $ n = p_{1}. p_{2}. p_{3}... p_{t} = q_{1}. q_{2}. q_{3}... q_{u}...(1)$

$\Rightarrow \exists k_{1}\in \mathbb{N}: q_{u}. k_{1} = p_{1}. p_{2}. p_{3}... p_{t} = q_{1}. q_{2}. q_{3}... q_{u}$.

$\Rightarrow \exists p_{i} \wedge \exists k_{2}\in \mathbb{N}: q_{u}. k_{2} = p_{i}$ (Since $q_{u}$ is a prime number that divides a product).

$\Rightarrow q_{u} = p_{i}$ and $k_{2} = 1$ (Since $p_{i}$ is a prime number).

Dividing the equation (1) by $q_{u} = p_{i}$ and renumbering the p's (if necessary) gives:

$q_{u} = p_{t};\, p_{1}. p_{2}. p_{3}... p_{t-1} = q_{1}. q_{2}. q_{3}... q_{u-1} < n$

$\Rightarrow p_{1}. p_{2}. p_{3}... p_{t-1} = q_{1}. q_{2}. q_{3}... q_{u-1} \in X$\ $\Rightarrow t-1 = u-1; \, p_{1} = q_{1}, p_{2} = q_{2}, p_{3} = q_{3},..., p_{t-1} = q_{u-1}$ $\Rightarrow t = u\, p_{1} = q_{1}, p_{2} = q_{2}, p_{3} = q_{3},..., p_{t-1} = q_{u-1}, p_{t} = q_{u}\Leftrightarrow n \in X$.

Therefore, we have proved that: Given $n (\geq 2) \in \mathbb{N}: (m \in X, \forall m < n\Rightarrow n \in X)$

$\Rightarrow X = \mathbb{N}$ (By The Second Principle of Induction).

$\therefore$ Every natural number greater than 1 can be decomposed in prime factors.

$\endgroup$
3
  • $\begingroup$ Welcome to MSE. Your answer isn't really an answer since this is a proof-verification question. $\endgroup$ Jan 14, 2019 at 18:52
  • $\begingroup$ Well, from my answer the question is solved. $\endgroup$
    – John M-D94
    Jan 14, 2019 at 18:55
  • $\begingroup$ Thanks for for the comment. $\endgroup$
    – John M-D94
    Jan 14, 2019 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .