# Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki.

Suppose $n$ has two prime factorizations: $\color{seagreen}{n} = p_1 p_2 \dots p_r = \color{seagreen}{q_1 q_2 \dots q_s} \quad (♯)$
where $r \le s$. Each $p_i$ and $q_j$ is prime with $p_1 \le p_2 \le \dots \le p_r$ and $q_1 \le q_2 \le \dots \le q_s$.

(1) Do I need to repine over exponents in these two prime factorizations? Why does page 2 and - Elementary Number Theory, Jones, p22, Theorem 2.3 - use them?

By reason of (♯), $p_1 \mathop \backslash \; \color{seagreen}{n = q_1 q_2 \dots q_s}$. By cause of Euclid's Lemma, $p_1 = q_j$ for some $1 \le j \le s$. Thus $p_1 \ge q_1$.

Similarly, since $q_1 \mathop \backslash \; n = p_1 p_2 \dots p_r$, from Euclid's Lemma, $q_1 \ge p_1$

(2) Can someone please amplify these steps? Where did $q_j$ hail from? Was $q_1$ switched with $q_j$? What ratified the right to do this?

Thus, $p_1 = q_1$, so cancel these [[Definition:Common Divisor of Integers|common factors]], which gives: $p_2 p_3 \cdots p_r = q_2 q_3 q_r \quad q_{r+1} \dots q_s$ Repeat this process to show: $p_2 = q_2, p_3 = q_3, \ldots, p_r = q_r$

If $r < s$, we arrive at $1 = q_{r+1} q_{r+2} \cdots q_s$ after canceling all [[Definition:Common Divisor of Integers|common factors]].

But by Divisors of One, the only divisors $1$ are $1$ and $-1$. Hence $q_{r+1}, q_{r+2}, \ldots, q_s$ cannot be prime numbers. Contradicton.

(3) In the last paragraph, is the proof showing $q_k = 1 \, or -1$ for all $r + 1 \le k \le s$?
$\pm 1$ isn't prime, thence this is a contradiction?

• I don't know the word "repine". – Mario Carneiro Apr 7 '14 at 7:20
• @MarioCarneiro It means 'fret' - I wanted to be more formal about it - this proof's formal. – Dwayne E. Pouiller Apr 7 '14 at 7:31
• Haha, I guess we have slightly different interpretations of the term "formal proof". – Mario Carneiro Apr 7 '14 at 7:33

2. Euclid's lemma says that if $p\mid ab$, then $p\mid a$ or $p\mid b$. By iterating this via some induction, you get the statement that if $p\mid q_1q_2\dots q_n$, then $p\mid q_j$ for some $1\le j\le n$. Applying this to the given case, $p\mid q_j$, but $q_j$ is prime, so $p=q_j$ (since the only divisors of a prime are that number and $1$, and $1$ isn't prime). Thus $p=q_j\ge q_1$, since the $q_i$'s are in increasing order.
3. Yes. Every $q_i$ for $r<i\le s$ divides $1$, which is a contradiction, since no prime divides $1$ and the $q_i$'s are assumed to be prime. Thus there are no such numbers, so $r\ge s$ (and repeating the process the other way around, you get $r\le s$).
In response to "can we swap $q_j$ with $q_i$ like the other proof": No, we can't use that directly in the ProofWiki proof, because they make use of the order independence in two different ways. In the ProofWiki proof, we use order independence to reorder the factors into nondecreasing order right at the start, then use the nondecreasing property to prove that the two sequences are the same. In the PDF, the sequences are not assumed to be in any particular order; instead we successively reorder the second sequence to look like the first by a sequence of swaps, thus establishing that they are the same sequence up to ordering. The usage of swaps there is necessary, as is the use of inequalities in each direction in the ProofWiki version; each was mandated by the earlier choice for how to represent the list of primes.
• Thanks. Upvote. Is it possible to prove $p_1 = q_1$ by switching $q_j$ and $q_1$? That's what the other proof does but Proofwiki doesn't? And can you please answer in your answer (and not in comments)? – Dwayne E. Pouiller Apr 7 '14 at 7:37