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_{1}, I_{2}, ..., 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_{1} = 2^{a1}·3^{b1}·5^{c1}·...,

I_{2} = 2^{a2}·3^{b2}·5^{c2}·...,

...

I_{j} = 2^{aj}·3^{bj}·5^{cj}·...,

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*