The Fundamental Theorem of Arithmetic

We are ready to prove Theorem 1.1.6 using the following idea. Suppose we have two factorizations of $n$ . Using Theorem 1.1.19 we cancel common primes from each factorization, one prime at a time. At the end, we discover that the factorizations must consist of exactly the same primes. The technical details are given below.

Proof. If $n=1$ , then the only factorization is the empty product of primes, so suppose $n>1$ .

By Proposition 1.1.20, there exist primes $p_1,\ldots, p_d$ such that

$$n = p_1 p_2 \cdots p_d.$$

Suppose that

$$n = q_1 q_2 \cdots q_m$$

is another expression of $n$ as a product of primes. Since

$$p_1 \mid n = q_1 (q_2 \cdots q_m),$$

Euclid's theorem implies that $p_1 = q_1$ or $p_1 \mid q_2\cdots q_m$ . By induction, we see that $p_1 = q_i$ for some $i$ .

Now cancel $p_1$ and $q_i$ , and repeat the above argument. Eventually, we find that, up to order, the two factorizations are the same. $\qedsymbol$