Proving the fundamental lemma of Arithmetic

Proving the fundamental lemma of Arithmetic

Last time I blogged I wrote about why proofs are so difficult. This time we should try to prove something a little more complicated and see if we can get some of the thoughts behind the proof while doing it to see if it really requires that amount of insights or part of a proof can be done by using more or less common sense. My guess is that we can come far with common sense, but we at some point need to rely on some insights or methods we have seen before.

So lets dive right into it and try to prove the fundamental lemma of arithmetic which states

Any integer greater than 1 can be written as a unique product (up to the ordering of the factors) of prime numbers.

Following the flow chart I posted a while ago on how to approach this it states that first we should understand the problem. I think we do that. I mean the problem states that there for every integer exists a unique prime factorization. For example

12 = 2 x 2 x 3

It certainly have a prime factorization and I can only find one of them. Well I think it is fairly easy to understand. So we need to break this into chunks. Due to the formulation it is not very clear but I see two claims.

  1. Every integer has a prime factorization – existence
  2. Every integer can only be represented in one way using a prime factorization – uniqueness

So these are the two parts I see from the lemma.

Existence

Let us prove the existence first. The way I usually do something like this is ask different questions and see if some of it looks promising. I can’t see a direct way through and I can’t see a way to prove it as a contrapositive.

However, when I asked myself “what does it mean if there exists a number that does not have a prime factorization?”. Before answering that, we need a few definitions. A number N is a prime if 1 and N are the only factors of the number. Otherwise the number is composite.

If a number is a prime then there cannot not exist a prime factorization of the number, since it is the number itself. Thus proving that it exists for all prime numbers. If a number is composite then it must exist a factorization of the number since otherwise it would be a prime. However if the factorization is not a prime factorization at least one of the numbers in the factorization must be a composite number.  For 12 we could make a factorization 12 = 3×4. Do you see where this leads?

This leads us to a place where it would be rather good to pull a well known method from induction called minimal counterexample out of the toolbox. This is where experience and knowledge of different methods comes in handy.

If there exist numbers without a prime factorization then there must be a smallest one of those numbers.  Let us call this s. (This is the basis of the minimal counterexample). From here on I believe that we use common sense logic again.

This number must have a factorization consisting of at least one composite number. For this composite number there are two options:

  1. It has a prime factorization – in which case we can replace the number with the prime factorization which means that s is in fact not a number without a prime factorization
  2. It has a factorization which includes a composite number. This means that s is not the smallest integer without a prime factorization which leads to a contradiction of the assumption that s is the smallest integer without a prime factorization.

Uniqueness

This part seems more difficult to me than the last part. What would happen if we try the same approach as before? So let’s ask “What happens if it is not true?”.

Well then exists a smallest number s that has has two prime factorizations

Since it is the smallest such number then there exists no pi = qj since otherwise we could generate a smaller number s/pi which would also have two prime factorisations.

Now comes the difficult part, proving that this assumption leads to a contradiction. First time I tried to prove it I ended up doing a whole lot of hand weaving which didn’t result in a proof. I tried to argue that there should be a subset of p’s and q’s such that the product was equal. And that sort of contradicted my assumption that s was the smallest number. I couldn’t fare that way.

At this point I was stuck for a while and this will happen once in a while. If we want to go through with the minimal counterexample way we need to construct a smaller number which will also have two prime factorisations such that we end up having a contradiction. For this  next step I must admit that this is where experience comes into play, and I have no idea how I came to think of it. I have seen something similar in another proof at one time, so I thought why not try that.

Let us assume that the p’s and q’s are ordered such that when i < j and the same thing goes for the q’s. Next thing we can assume that p1 < q1.  If q1 < p1 we can make the same argument for q instead. One note is that we can be certain they are not equal.

Now we can represent

where k is an integer such that . Since if follows that . What good does that do us. Well we can now represent s as

where both terms of the sum are positive integers. But where does that lead us? Well we now have two representations that both include p1.

We can now construct a smaller number t

This shows that p1 is a factor of t. And since it is a prime, it will also be in the prime factorization.

At the same time we can represent

which apart from r is a prime factorization of the number t. Since we have established earlier that we know that p1 cannot be a prime factor of r. This means that if we replace r with it’s prime factorization we have a prime factorization of t where p1 is not included. Thus we have a number t < s for which we have a prime factorisation with and without p1. Thus there is a number smaller than s which has two prime factorisations which contradicts the assumption that s was the smallest such number.

Wrapping up

We have not proven both existence and uniqueness of the prime factorisation of all natural number larger than 1. Thus proving the theorem.

When I started writing this post I was sure that I could easily prove this lemma since I had most of it in my head already. After brushing through the existence part I must admit that I spent quite a while with pen and paper doing  the uniqueness part and based it on something I had seen before. I believe this is where experience comes into play.

Indeed wikipedia states that Proof of existence of a prime factorization is straightforward; proof of uniqueness is more challenging.

My conclusion is that yes proofs are bloody difficult, but like anything else practice will give you a set of tools to attack it, and many hours of hard work and studying will make you a master. However, I also want to stress that there is indeed no magic involved.

The image of the thinker is taken by Todd Martin and shared under the creative commons license.

Posted by Kristian

Leave a Reply