8.4: The Fundamental Theorem of Arithmetic

There is an important fact about primes that you probably already know: every positive integer number has a unique prime factorization. So every positive integer can be built up from primes in exactly one way. These quirky prime numbers are the building blocks for the integers.

Since the value of a product of numbers is the same if the numbers appear in a different order, there usually isn’t a unique way to express a number as a product of primes. For example, there are three ways to write 12 as a product of primes:

\[\nonumber 12 = 2 \cdot 2 \cdot 3 = 2 \cdot 3 \cdot 2 = 3 \cdot 2 \cdot 2.\]

What’s unique about the prime factorization of 12 is that any product of primes equal to 12 will have exactly one 3 and two 2’s. This means that if we sort the primes by size, then the product really will be unique.

Let’s state this more carefully. A sequence of numbers is weakly decreasing when each number in the sequence is at least as big as the numbers after it. Note that a sequence of just one number as well as a sequence of no numbers—the empty sequence —is weakly decreasing by this definition.

Theorem \(\PageIndex{1}\)

[Fundamental Theorem of Arithmetic] Every positive integer is a product of a unique weakly decreasing sequence of primes.

For example, 75237393 is the product of the weakly decreasing sequence of primes

\[\nonumber 23, 17, 17, 11, 7, 7, 7, 3,\]

and no other weakly decreasing sequence of primes will give 75237393.⁶

Notice that the theorem would be false if 1 were considered a prime; for example, 15 could be written as \(5 \cdot 3\), or \(5 \cdot 3 \cdot 1\), or \(5 \cdot 3 \cdot 1 \cdot 1, \ldots \)

There is a certain wonder in unique factorization, especially in view of the prime number mysteries we’ve already mentioned. It’s a mistake to take it for granted, even if you’ve known it since you were in a crib. In fact, unique factorization actually fails for many integer-like sets of numbers, such as the complex numbers of the form \(n + m \sqrt{-5}\) for \(m, n \in \mathbb{Z}\) (see Problem 8.25).

The Fundamental Theorem is also called the Unique Factorization Theorem, which is a more descriptive and less pretentious, name—but we really want to get your attention to the importance and non-obviousness of unique factorization.

Proving Unique Factorization

The Fundamental Theorem is not hard to prove, but we’ll need a couple of preliminary facts.

Lemma 8.4.2. If \(p\) is a prime and \(p \mid ab\), then \(p \mid a\) or \(p \mid b\).

Lemma 8.4.2 follows immediately from Unique Factorization: the primes in the product \(ab\) are exactly the primes from \(a\) and from \(b\). But proving the lemma this way would be cheating: we’re going to need this lemma to prove Unique Factorization, so it would be circular to assume it. Instead, we’ll use the properties of gcd’s and linear combinations to give an easy, noncircular way to prove Lemma 8.4.2.

Proof. One case is if \(\text{gcd}(a, p) = p\). Then the claim holds, because \(a\) is a multiple of \(p\).

Otherwise, \(\text{gcd}(a, p) \neq p\). In this case \(\text{gcd}(a, p)\) must be 1, since 1 and \(p\) are the only positive divisors of \(p\). Now \(\text{gcd}(a, p)\) is a linear combination of \(a\) and \(p\), so we have \(1 = sa + tp\) for some \(s, t\). Then \(b = s(ab) + (tb)p\), that is, \(b\) is a linear combination of \(ab\) and \(p\). Since p divides both ab and p, it also divides their linear combination \(b. \quad \blacksquare\)

A routine induction argument extends this statement to:

Lemma 8.4.3. Let \(p\) be a prime. If \(p \mid a_1a_2 \cdots a_n\), then \(p\) divides some \(a_i\).

Now we’re ready to prove the Fundamental Theorem of Arithmetic.

Proof. Theorem 2.3.1 showed, using the Well Ordering Principle, that every positive integer can be expressed as a product of primes. So we just have to prove this expression is unique. We will use Well Ordering to prove this too.

The proof is by contradiction: assume, contrary to the claim, that there exist positive integers that can be written as products of primes in more than one way. By the Well Ordering Principle, there is a smallest integer with this property. Call this integer \(n\), and let

\[\begin{aligned} n &= p_1 \cdot p_2 \cdots p_j, \\ &= q_1 \cdot q_2 \cdots q_k, \end{aligned}\]

where both products are in weakly decreasing order and \(p_1 \leq q_1\).

If \(q_1 = p_1\), then \(n / q_1\) would also be the product of different weakly decreasing sequences of primes, namely,

\[\begin{aligned} p_2 \cdots p_j, \\ q_2 \cdots q_k, \end{aligned}\]

Since \(n / q_1 < n\), this can’t be true, so we conclude that \(p_1 < q_1\).

Since the \(p_i\)’s are weakly decreasing, all the \(p_i\)’s are less than \(q_1\). But

\[\nonumber q_1 \mid n = p_1 \cdot p_2 \cdot p_j,\]

so Lemma 8.4.3 implies that \(q_1\) divides one of the \(p_i\)’s, which contradicts the fact that \(q_1\) is bigger than all them. \(\quad \blacksquare\)

 

⁶The “product” of just one number is defined to be that number, and the product of no numbers is by convention defined to be 1. So each prime, \(p\), is uniquely the product of the primes in the lengthone sequence consisting solely of \(p\), and 1, which you will remember is not a prime, is uniquely the product of the empty sequence.