Unique factorization? A Math question for the weekend?

Question

Consider the integer 100. It can be completely factored like so:

2^2 x 5^2

Next, consider 3663. It can be completely factored like so:

3^2 x 11 x 37

Finally, consider the integer 31. It is prime, but it can be "completely factored" as just itself, namely 31.

As far as I can tell all these factorizations are unique. Except for the order of the factors, they can be done in one and only one way.

So, prove that the complete factorization of *any* integer into primes is unique.

Charles

Answer 1

The proof consists of two steps. In the first step every number is shown to be a product of zero or more primes. In the second, the proof shows that any two representations may be unified into a single representation.

Non-prime composite numbers

Suppose there were a positive integer which cannot be written as a product of primes. Then there must be a smallest such number: let it be n. This number n cannot be 1, because of the convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus

n = ab
where both a and b are positive integers smaller than n. Since n is the smallest number which cannot be written as a product of primes, both a and b can be written as products of primes. But then

n = ab
can be written as a product of primes as well, a contradiction. This is a minimal counterexample argument.

Unique Composition

The uniqueness part of the proof hinges on the following fact: if a prime number p divides a product ab, then it divides a or it divides b (Euclid's lemma). This is a lemma, to prove first. For that, if p doesn't divide a, then p and a are coprime and Bézout's identity yields integers x and y such that

px + ay = 1.
Multiplying with b yields

pbx + aby = b,
and since both summands on the left-hand side are divisible by p, the right-hand side is also divisible by p. That proves the lemma.

Given two products of primes which are equal, take any prime p from the first product. It divides the first product, and hence also the second. By the above fact, p must then divide at least one factor in the second product. But the factors are all primes themselves, so p must actually be equal to one of the factors of the second product. So p can be cancelled from both products. Continuing in this fashion, eventually the prime factors of the two products must match up precisely.

Answer 2

First, any prime will have unique factorization. Any non prime integer N will be the product of primes < N . Because each sucessive non-prime integer is unique it will inturn require a unique product of primes.

Answer 3

If complete factorization were not unique, recombination of factors would result in more than one integer. Without error, this is not possible.

Answer 4

go read this:
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic