Theorem. Fundamental Theorem of Arithmetic [0052]

For any natural number there exists a unique finite series of primes such that .

Proof. To show existence we perform induction over . If there is nothing to show. Thus let . If is prime there is nothing to show, so let be not prime. In that case ther exist with By induction hypothesis and are themselves products of primes, and by extension as well.

To show uniqueness we assume two factorizations and . Without loss of generality we assume that . By Euclid's Lemma there exists such that thus . We now perform induction over . if then must also be 1, since dividing by shows that is contradictory otherwise. For we can divide both sides by (since ) and apply the induction hypothesis.