Appendix A Proof of the Fundamental Theorem of Arithmetic

The purpose of this appendix is to present a proof of Theorem 4.6.5:

every natural number greater than or equal to $2$ can be expressed as a

product of primes; this product is unique up to the order of the factors.

This result may seem obvious, because we were all taught it at an early age; so before we prove it, perhaps it is worth considering why it requires proof.

The point is that there are systems other than $\mathbb{N}$ where the corresponding statement fails to be true. For example, let $A$ be the set of all natural numbers of the form $4m+1$, so that $A=\{1,5,9,13,\dots\}$. The product of any two elements of $A$ is itself in $A$, since

Thus we have a perfectly good multiplication defined on $A$, and we can define a ‘‘prime number in $A$’’ to be an element of $A$, not equal to $1$, whose only divisors in $A$ are $1$ and itself. It turns out that every element of $A$ (except $1$) can be written as a product of primes in $A$; but we have $441=9\cdot 49=21\cdot 21$, and each of the numbers $9$, $49$ and $21$ is prime in $A$. (They are clearly not prime in $\mathbb{N}$, as $9=3\cdot 3$, $49=7\cdot 7$ and $21=3\cdot 7$ — but $3,7\not\in A$.) Thus although we have multiplication in $A$, primes in $A$ and prime factorization in $A$, we do not have uniqueness of prime factorization in $A$.

Now, to prove Theorem 4.6.5, for a natural number $n\geqslant 2$, consider the following two statements:

 $P(n)\colon$

‘‘$n$ can be written as a product of primes’’;

 $Q(n)\colon$

‘‘there is only one way of writing $n$ as a product of primes, up to the order of
   the factors’’.

We shall use the Generalized Principle of Induction to prove that $P(n)$ and $Q(n)$ are true for each $n\geqslant 2$.

Basis of induction: the number $2$ is prime, so $P(2)$ is satisfied by our convention that a single prime number is considered a product of primes; further, there is clearly no other way that $2$ can be written as a product of primes, so $Q(2)$ is also satisfied.

Induction step: let $n\geqslant 2$, and assume inductively that $P(k)$ and $Q(k)$ are true for each $k\in\{2,3,\ldots,n\}$; we must prove that $P(n+1)$ and $Q(n+1)$ are true. If $n+1$ is prime, then $P(n+1)$ and $Q(n+1)$ are certainly true, just as in the basis of induction above.

Otherwise $n+1$ is composite. In this case we verify each of the statements $P(n+1)$ and $Q(n+1)$ separately.

$P(n+1)\colon$ Since $n+1$ is composite, we can write $n+1=ab$, where $a,b\in\{2,3,\ldots,n\}$. By the induction hypothesis, $P(a)$ and $P(b)$ are true, so we can write both $a$ and $b$ as products of primes, say $a=p_{1}\cdots p_{r}$ and $b=q_{1}\cdots q_{s}$, where $r,s\in\mathbb{N}$ and $p_{1},\ldots,p_{r},q_{1},\ldots,q_{s}$ are prime numbers. This implies that $n+1$ can be written as a product of primes because

and so $P(n+1)$ is true.

$Q(n+1)\colon$ Suppose that

where $r,s\in\mathbb{N}$ and $p_{1},p_{2},\ldots,p_{r},q_{1},q_{2},\ldots,q_{s}$ are prime numbers. We must show that $r=s$ and that the primes $p_{1},p_{2},\ldots,p_{r}$ are the same as $q_{1},q_{2},\ldots,q_{s}$ (except for the order).

Now $p_{1}$ divides $n+1=q_{1}q_{2}\cdots q_{s}$, and so, as observed in Remark 4.6.4, we have $p_{1}|q_{j}$ for some $j\in\{1,2,\ldots,s\}$. As $q_{j}$ is prime and $p_{1}>1$, this implies that $p_{1}=q_{j}$. If we set $m=(n+1)/p_{1}\in\{1,2,\ldots,n\}$, then we can write

Note that $m\neq 1$ because

contradicting our assumption that $n+1$ is composite. Hence $m\in\{2,3,\ldots,n\}$, so that $Q(m)$ is true by the induction hypothesis. Thus the two prime factorizations of $m$ in (A) are the same (up to reordering); that is, $r-1=s-1$ and $p_{2},p_{3},\ldots,p_{r}$ are the same as $q_{1},q_{2},\ldots,q_{j-1},q_{j+1},\ldots,q_{s}$ (except for the order). Hence we conclude that $r=s$ and, inserting $p_{1}=q_{j}$ in the lists, that $p_{1},p_{2},\ldots,p_{r}$ are equal to $q_{1},q_{2},\ldots,q_{s}$ (except for the order). This proves that $Q(n+1)$ is satisfied, and thus the result holds by mathematical induction. $\Box$