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.