## 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 2a·3b·5c·..., 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 I1, I2, ..., Ij. We observe that each factor Ii is less than or equal to n. By the induction hypothesis, each is uniquely factorable.

Let I1 = 2a1·3b1·5c1·...,

I2 = 2a2·3b2·5c2·...,

...

Ij = 2aj·3bj·5cj·...,

where all of the ai's, bi's, ci's, ... are non-negative integers.

To simplify the notation, let A = ∑i=1j ai, B = ∑i=1j bi, C = ∑i=1j ci, and so on. So we have

(1) n + 1 = 2A·3B·5C·...·pP·...

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 = 2A'·3B'·5C'·...·pP'·...

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 pP evenly divides n + 1, and from (2) that pP'|(n + 1).

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

QED

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

cactuspear home