# Is this proof of the uniqueness of prime factorizations unnecessarily long?

I am learning textbook Analysis I by Herbert Amann and Joachim Escher. The authors present Prime Factorization Theorem

and a proof of uniqueness

On the basis of authors' proof, I have found a shorter way to fulfill the task as follows:

Let p be the least such number with prime factorizations $$p = p_0 p_1 \cdots p_k = q_0 q_1 \cdots q_n$$. We have $$p_i \neq q_j$$ for all $$i$$ and $$j$$, since any common factor could be divided out to give a smaller natural number $$p'$$ with two different prime factorizations, in contradiction to the choice of $$p$$.

We can suppose that $$p_0 ≤ p_1 ≤ \cdots ≤ p_k$$ and $$q_0 ≤ q_1 ≤ \cdots ≤ q_n$$ as well as $$p_0 < q_0$$.

(I quote these two paragraphs from authors' work)

Clearly, $$p_0 \mid p$$. It follows from $$p_0 < q_0 ≤ q_1 ≤ \cdots ≤ q_n$$ and $$p_0, q_0, q_1, \cdots, q_n$$ are all prime numbers that $$p_0 \not \mid q_j$$ for all $$j$$. Then $$p_0 \not \mid q_0 q_1 \cdots q_n$$ and thus $$p_0 \not \mid p$$, which is a contradiction.

1. I would like to ask if my modification of authors' proof is correct. I can not understand why the authors did not take this shorter approach.

2. In the proof, the authors said that

Consequently we have the prime factorization $$p − q = p_0 r_1 \cdots r_l$$ for some prime numbers $$r_1 ,\cdots,r_l$$.

It seems to me that this statement is not correct since it maybe the case that $$r_1=\cdots=r_l=1$$, which are not prime numbers. Is my understanding of this statement correct?

1. Your proof uses the following fact: if $$p_0$$ is prime and $$p_0\nmid a$$, $$p_0\nmid b$$, then $$p_0\nmid ab$$. While this is not a very advanced number theory fact, it does require proof given the standard (in my experience) definition of a prime as a number having exactly two positive divisors. It's quite possible that the proof of uniqueness of factorizations that you included was designed to not use this fact (perhaps the author wanted it to appear earlier in the book than that fact).
2. Usually, mathematicians deem notation like this to include the possibility that $$l=0$$, that is, that there are no $$r$$s and that $$p-q=p_0$$.
• In the proof, there is also a sentence Write $q_0 − p_0$ as a product of prime numbers: $q_0 − p_0 = t_0 \cdots t_s$. Now $0$ belongs to the set of indexes. According to your answer, $t_i \neq 1$ for all $i$. IMHO, there exists a case where $q_0=3,p_0=2$ and thus $q_0-p_0=1$. Please verify my observation! Thank you for your help! Mar 13, 2019 at 8:31
• @LeAnhDung: In that situation, the product is empty; basically, $s=-1$. Mar 14, 2019 at 16:29