The Fundamental Theorem of Arithmetic states the following:

*Every integer greater than 1 can be represented uniquely as the product of prime numbers.*

Another way to put this is that every integer has a unique factorization. For example, 60 factors into , and there is only way way to do this factorization using prime numbers. (Rearranging the order of the numbers doesn’t count as a different factorization.)

In this post we’ll prove the Fundamental Theorem of Arithmetic. There are two parts: (1) Proving that every integer greater than 1 can be represented as the product of prime numbers (i.e., existence), and (2) Proving that this representation is unique (i.e., uniqueness).

Reminder: A prime number is a positive integer that is divisible by exactly two positive integers: itself and 1.

**First, Existence**. Suppose, by way of contradiction, that there is some positive integer that cannot be represented as the product of primes. Then there is a smallest such number *N*. If *N* cannot be represented as a product of primes then *N* cannot itself be prime. Thus there exist two positive integers *a* and *b*, with , such that . Since *a* and *b* are both positive integers smaller than *N* they must each be the product of primes, where , , and and are primes for each *i* and *j*. But then and thus also is the product of primes.

**Second, Uniqueness**. For this we need a lemma that isn’t hard to prove:

Lemma: If a prime *p* divides an integer , then *p *divides *a* or *p* divides *b*.

Now, let *N* be a positive integer. Suppose there exist two ways to represent *N* as the product of primes,

,

where and are primes for each *i* and *j*. Assume, without loss of generality, that these representations are ordered, so that and for all *i* for which these inequalities are defined.

Suppose and . Then , a contradiction. Similarly, if and , we have a contradiction.

Now, let *i* be the first index for which . If *i* exists then , by the argument in the previous paragraph. We can assume, without loss of generality, that . We have that . Since , we also have . By the lemma, divides for some *j*, . But each of the values is prime and so is only divisible by 1 and itself. Since , we have a contradiction.

Thus there is no index *i* for which . Our argument two paragraphs above shows that we can’t have this and or . Thus , and so the two representations, and , are identical.