## The Fundamental Theorem of Arithmetic

We shall prove in this section the following result.

Theorem 1.5.7 (Fundamental Theorem of Arithmetic)   If is an integer then

where are primes and , , ..., are integers. Furthermore, this representation of is unique.

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

Proposition 1.5.8 (Euclid's First Theorem)   An integer is prime if and only if it satisfies the following property: for all integers , implies or .

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.

Corollary 1.5.9 (of Euclid's First Theorem)   Let be a prime. For any integers , implies or or ... or .

We also need the following basic result.

Lemma 1.5.10   If is an integer then the smallest which divides must be a prime number.

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 but not necessarily in any particular order and the are non-negative integers. (By allowing the exponents to be 0, we can insert dummy prime factors'' so that it looks as though both sides run over the same set of primes.)

We 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.

Theorem 1.5.11   Let and be any positive integers with the given prime factorizations (, for all , ). Then the following is true:
• if and only if , for all ,

• , where ,

• , where .

David Joyner 2007-09-03