# Acquiring Cache Money

The hot problems of an immature undergrad student.

## a simple proof: fta(rithmetic)

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 = p1p2p3…pn and b = q1q2q3…qm, where the pi’s and qj’s are prime numbers (i = 1, …, n and j = 1, …, m). That means k = p1p2p3…pnq1q2q3…qm, 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 a1, a2, …, an be integers. Then if p divides the product a1a2…an, then p must divide aj 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 = p1p2…pn and s = q1q2…qm.

Then p1p2…pn = q1q2…qm. 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:

pi1pi2…pik = qj1qj2…qjl

Clearly pi1 divides the left hand side. Then since these two quantities are equal, pi1 must also divide the right hand side. So by our earlier statement, pi1 must divide qjx 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.

1. whatilearninmath reblogged this from sebanie and added:
part 2 of discrete math (toc) Sorry for the lack of posts—I’ve been doing some stuff related to my second major. To make...
2. sebanie posted this