Proof of the Fundamental Theorem of Arithmetic

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 2^2 \cdot 3 \cdot 5, and there is only one 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 1 < a \leq b < N, such that N = ab.  Since a and b are both positive integers smaller than N they must each be the product of primes, where a = p_1 p_2 \cdots p_m, b = q_1 q_2 \cdots q_n, and p_i and q_j are primes for each i and j.  But then N = p_1 p_2 \cdots p_m q_1 q_2 \cdots q_n 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 ab, then 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,

N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n,

where p_i and q_j are primes for each i and j.  Assume, without loss of generality, that these representations are ordered, so that p_i \leq p_{i+1} and q_i \leq q_{i+1} for all i for which these inequalities are defined.

Suppose p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_m and n > m.  Then  N = p_1 p_2 \cdots p_m < q_1 q_2 \cdots q_n = N, a contradiction.  Similarly, if  p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_n and m > n, we have a contradiction.

Now, let i be the first index for which p_i \neq q_i.  If i exists then i \leq \min\{m,n\}, by the argument in the previous paragraph.  We can assume, without loss of generality, that p_i < q_i.  We have that p_1 p_2 \cdots p_{i-1} = q_1 q_2 \cdots q_{i-1}.  Since p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n, we also have p_i \cdots p_m = q_i \cdots q_n.  By the lemma, p_i divides q_j for some j, i \leq j \leq n.  But each of the q_j values is prime and so is only divisible by 1 and itself.  Since p_i < q_i \leq q_j, we have a contradiction.

Thus there is no index i for which p_i \neq q_i.  Our argument two paragraphs above shows that we can’t have this and m < n or m > n.  Thus m = n, and so the two representations, p_1 p_2 \cdots p_m and q_1 q_2 \cdots q_n, are identical.

Advertisements
This entry was posted in arithmetic. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s