fundamental theorem of arithmetic

The Fundamental Theorem of Arithmetic (also known as the Unique Factorization Theorem) says that every integer greater than 1 can be expressed in one and only one way as the product of primes.

In more formal language, there is a one-to-one correspondence between the positive integers and the set of all products of the form 2^a·3^b·5^c·..., where a, b, c, ... are non-negative integers.

Proof: We use a form of the induction hypothesis that says that if a proposition P is true for all positive integers less than or equal to n implies that P is true for n + 1, then P is true for all integers.

Let P(n) be the proposition that n can be uniquely factored. If n + 1 is prime, then it is uniquely factorable as 1 times n + 1, and we are done. Otherwise, n + 1 is the product of some finite set of integers I₁, I₂, ..., I_j. We observe that each factor I_i is less than or equal to n. By the induction hypothesis, each is uniquely factorable.

Let I₁ = 2^a₁·3^b₁·5^c₁·...,

I₂ = 2^a₂·3^b₂·5^c₂·...,

...

I_j = 2^a_j·3^b_j·5^c_j·...,

where all of the a_i's, b_i's, c_i's, ... are non-negative integers.

To simplify the notation, let A = ∑_i=1^j a_i, B = ∑_i=1^j b_i, C = ∑_i=1^j c_i, and so on. So we have

(1) n + 1 = 2^A·3^B·5^C·...·p^P·...

Next we show that the above factorization of n + 1 is unique. By contradiction, assume that there is some other factorization of n + 1, such as

(2) n + 1 = 2^A'·3^B'·5^C'·...·p^P'·...

To show that A = A', B = B', ..., P = P', ...

Without loss of generalization, suppose that the power P of the prime p in (1) is not equal to the power P' of the same prime p in (2). We know from (1) that p^P evenly divides n + 1, and from (2) that p^P'|(n + 1).

If P' > P, we have p^P'-P|(n + 1)/p^P. But by (1), the only factors of (n + 1)/p^P are primes other than p, a contradiction. Using a similar argument, if P' < P, we have p^P-P'|(n + 1)/p^P', contradicting (2).

QED

Sources: wikipedia.org and Paul R Halmos, Naive Set Theory