# How to prove every integer's prime factorization is unique up to the ordering of its prime factors?

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.

• And what exactly is the question? – Old John Dec 6 '13 at 21:38
• 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. – cebroski Dec 6 '13 at 21:39
• Then it might be better to edit this into the post to make it clear that you are asking a question. – Old John Dec 6 '13 at 21:40
• 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. – André Nicolas Dec 6 '13 at 22:12

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

• 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$. – jiten Jan 29 '18 at 16:05
• 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. – Cameron Buie Jan 29 '18 at 19:09

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.

• Welcome to MSE. Your answer isn't really an answer since this is a proof-verification question. – José Carlos Santos Jan 14 '19 at 18:52
• Well, from my answer the question is solved. – John M-D94 Jan 14 '19 at 18:55
• Thanks for for the comment. – John M-D94 Jan 14 '19 at 18:56