Acquiring Cache Money

Here is a fun-damental theorem that I think most people take for granted:

Any integer greater than 1 can be uniquely written (up to reordering) as a product of primes.

Some of you may know this as the Fundamental Theorem of Arithmetic. It’s pretty embarrassing that I didn’t know this was a theorem, or even that it was true, until my discrete math class in college. It’s also pretty embarrassing that I haven’t posted a blog entry on here for like a week or two, so I decided to make up for my incompetence by proving this theorem on my blog.

There are two parts to this proof: existence (every number has such a prime decomposition) and uniqueness (every number has only one prime decomposition). Before we begin the actual proof, though, we need the following piece of information:

Well-Ordering Principle: Every non-empty set of positive integers contains a smallest element.

That’s not hard to believe, right? I’ll give you time to convince yourself of this fact. Good? Good.

Let’s get started. How do you know this decomposition exists?

We’re going to prove this by contradiction. Let’s assume that this prime decomposition does not exist for every integer, and say we take all those nasty counterexamples and put them in a set C. Since this set of counterexamples is comprised of mere positive integers and thus a nonempty subset of the natural numbers, we know by the well-ordering principle that C has a minimal element. Let’s call this minimal element k.

We have two cases now: either k is prime or it is composite.

Case 1: k is prime. Then this already contradicts the fact that k is a counterexample, because it can indeed be written as a product of primes (itself). So let’s go to the next, more interesting case.

Case 2: k is composite. Then that means k = ab, for some positive integers a and b. Since we’re working with all positive integers, this implies that a and b are both less than k. Ah, but remember what this means: a and b can both be written as a product of primes. Why? Because k was the smallest integer that couldn’t be written as a product of primes, so the claim must hold for anything smaller than it.
Okay, let’s write a and b as a product of primes, shall we?
Let a = p₁p₂p₃…p_n and b = q₁q₂q₃…q_m, where the p_i’s and q_j’s are prime numbers (i = 1, …, n and j = 1, …, m). That means k = p₁p₂p₃…p_nq₁q₂q₃…q_m, thus contradicting again that k ∈ C.

But that means C doesn’t have a minimal element, because if it did, it can’t be an element of C. This can only mean that C is empty, so every element can be written as a product of primes, proving the existence of such a decomposition for all integers greater than 1!

Okay, fine; this decomposition exists. How do you know each number only has one?

I’m going to spit out some statements that need some proving, so I’ve left them as exercises to the reader. (Okay, fine, I proved them for you.)

First, let p be a prime, and a, b be integers. Then if p divides ab and p doesn’t divide a, then p divides b.

Using this fact and induction, we can show the following: let a₁, a₂, …, a_n be integers. Then if p divides the product a₁a₂…a_n, then p must divide a_j for some j between 1 and n (inclusive).

Now we can actually prove that if a number has a prime decomposition, it can only have at most one. Again we will do this by contradiction. Assume that a number s has more than one distinct prime decomposition, say

s = p₁p₂…p_n and s = q₁q₂…q_m.

Then p₁p₂…p_n = q₁q₂…q_m. We can cancel out all the common prime numbers from both sides to get another equation where no one prime appears on both sides. So:

p_i1p_i2…p_ik = q_j1q_j2…q_jl

Clearly p_i1 divides the left hand side. Then since these two quantities are equal, p_i1 must also divide the right hand side. So by our earlier statement, p_i1 must divide q_jx for some x between 1 and l. But this is impossible, as all of these numbers are distinct primes—a contradiction. Thus, every number can only have at most one prime decomposition! ■

And there you have it: the Fundamental Theorem of Arithmetic, a fact about numbers that most people probably already knew anyway.