Fundamental Theorem of Arithmetic

[Jamin2112]

Homework Statement

Theorem. (Fundamental Theorem of Arithmetic) Ever positive integer n has a prime factorization, which is unique except for reordering of the factors.

Homework Equations

6.8 Definition. A prime factorization of n expresses n as a product of powers of distinct primes; the exponent of each prime is its multiplicity. We write a prime factorization of n as n=$$\prod$$$$^{k}_{i=1}$$p_i^e_i.

The Attempt at a Solution

[PLAIN]http://icanhascheezburger.files.wordpress.com/2007/09/128320993454987500dudewaitw.jpg

If n is a prime, of course it has a prime factorization. n = n¹. I'm trying to find out how to construct a general proof.

Suppose n = p₁^e₁ * p₂^e₂ * ... * p_k^e_k

or something. Give me a jump-start.

 

[hgfalling]

Here are sketches of the proofs. You'll have to fill in the details however.

Two parts here: Existence (every positive integer has a prime factorization) and Uniqueness (that prime factorization is unique).

Existence is easy. Uniqueness is not as easy.

For existence, assume there are numbers that cannot be written as the product of primes. Then there must be a smallest such number. Show that this leads to a contradiction. (Hint: if the number were prime, it would automatically just be itself^1. So it must be composite, etc.)

For uniqueness, assume there are numbers that can be written as different products of primes. Again take the smallest such number. Write the two factorizations as products of primes. First prove that none of the prime factors can be the same between the two factorizations. Then, pick the smallest factor in either factorization. Divide one of the factors of the other factorization by the smallest factor (you get a remainder). Substitute the quotient + remainder into the factorization. Now show that the "remainder" part of the factorization also has two prime factorizations, which contradicts our assumption that this is the smallest such number.