We shall prove in this section the following result.

Before proving this result, we require a preliminary fact about primes.

**proof of Euclid's First Theorem**: (only if) We may assume that are non-zero. In this case, we have either or since is a prime. In the latter case, and we are done. By Proposition 1.2.16(3), , so if then .

(if) Assume for all integers , implies or . If was composite then , for some and . But would then imply or , both of which are impossible.

In fact, rather than using Euclid's First Theorem directly in the proof of the Fundamental Theorem of Arithmetic, we use the following consequence of it.

We also need the following basic result.

**proof of lemma**: Let be the smallest positive divisor of . Suppose has a factor with and . But and implies . Since is the smallest factor of which is greater than , we must have , so is prime.

**proof of Fundamental Theorem of Arithmetic**: First, we show that is a product of primes.

If is a prime then we are done, so we may assume is not a prime.

Let and let .

step 1: Let denote the smallest divisor of . (By the above lemma, is a prime.) Let . (Note: .)

step 2: If is prime then stop. If is not a prime then replace by and go to step 1.

Since , this process must eventually terminate. Say is a prime. Then

so is a product of primes.By arranging the primes in increasing order and grouping identical primes in the product together, we may write as in the statement of the theorem.

Now we prove uniqueness. Suppose

where the 's are distinct primes butWe may suppose that (some exponent must be greater than 0 since ). By the corollary to Euclid's First Theorem, we must have or or ... . Since the 's are distinct, the only possibility is if , so in particular . If then and the corollary to Euclid's First Theorem implies or ... . This is impossible since the 's are distinct. Similarly, leads to a contradiction. This leaves the only possibility , so

Proceeding inductively, we find , ..., . This proves uniqueness and the theorem.Many important results in number theory are proved using prime factorization. The following theorem is an immediate consequence of the Fundamental Theorem of Arithemetic. The proof is left as an exercise.

- if and only if , for all ,
- , where ,
- , where .

David Joyner 2007-09-03