This post is for people don't know much about mathematics but have heard of prime numbers and might be interested to learn more.

I want to tell you something about the natural numbers, and show you a proof about them which I hope you'll be able to follow. I'm going to try and introduce a few terms, so that you start becoming familiar with this stuff.

What are the natural numbers? The natural numbers are represented by the symbol *TeX Embedding failed!* and comprise the set *TeX Embedding failed!*. That is, the natural numbers are whole positive integers, and are the kind of numbers people are familiar with in the natural world hence the name. Sometimes *TeX Embedding failed!* isn't counted as a natural number, and there are several mathematical/philosophical arguments around this point. But in our case we will include *TeX Embedding failed!* in our definition of the natural numbers although we won't use it in what we are talking about. Notice that what we are doing here really has nothing to do with the "real world". We are talking about an abstract space of numbers which we've decided to call *TeX Embedding failed!* and we've decided that it only contains those numbers we specified. Pure mathematics is always like this, and any correlation with the real world is purely coincidence. When mathematics is used explicitly to model the real world, it is called physics.

Whenever I talk about numbers in the following sections, assume I mean the natural numbers as thus defined.

If you take any natural number, you can ask a question, can it be expressed as a product of factors?

A factor is just a whole number that divides another a whole number of times. And the word product is just another word for multiplication. So for example, if we consider the number *TeX Embedding failed!*, then *TeX Embedding failed!* is a factor of *TeX Embedding failed!* because *TeX Embedding failed!*, and *TeX Embedding failed!* is a whole number. *TeX Embedding failed!* is not a factor of *TeX Embedding failed!* because *TeX Embedding failed!* which is not a whole number.

Instead of thinking "what numbers divide *TeX Embedding failed!*", I usually like to think from the other angle which is "what numbers multiplied together, produce *TeX Embedding failed!*", which says exactly the same thing but in a slightly different way. So for example, we can say that *TeX Embedding failed!* is a factor of *TeX Embedding failed!* because *TeX Embedding failed!*. Do you see that we are saying exactly the same thing, but that there is a subtle difference in the way we look at it? You can look at it from either angle, depending on what you prefer.

Now the number *TeX Embedding failed!* has a lot of factors: *TeX Embedding failed!*, and *TeX Embedding failed!* are all factors of the number *TeX Embedding failed!* and this list is in fact all the possible factors of the number *TeX Embedding failed!*. How do I know that this is all the possible factors? Well, I just went through all the numbers starting from *TeX Embedding failed!* upto *TeX Embedding failed!* and worked out whether or not the number divided *TeX Embedding failed!* a whole number of times.

But if you look a little closer, there are some obvious facts about finding the list of factors for a number. The most obvious one is probably that any number bigger than the number, cannot be a factor. Any number bigger than *TeX Embedding failed!* cannot be a factor of *TeX Embedding failed!* since it will always be a fraction, which is not a whole number. For example *TeX Embedding failed!*, and *TeX Embedding failed!*, and so on.

Another fact we can observe about finding the factors of a number is that the numbers *TeX Embedding failed!* and the number itself are always factors, so we get those for "free" without having to do any calculations: we know that *TeX Embedding failed!* divides every number and a number always divides itself. *TeX Embedding failed!*, and *TeX Embedding failed!*. So really, to find all the factors of a number, we really only need to go through the numbers checking if they are divisors starting at the number *TeX Embedding failed!*.

I've just introduced a new term, divisor. This is what we call the number on the bottom, because it is doing the dividing of the number on the top. Another name for the number on the bottom is the denominator, and the name we use for the number on the top is the numerator.

Another fact about finding factors of a number is that we never have to check any further than half the number. For example, for the number *TeX Embedding failed!*, we never have to check any higher than *TeX Embedding failed!*. This is because any divisor that is bigger than half the numerator, cannot possibly divide the numerator a whole number of times (unless it is equal to the numerator). If the divisor divides the numerator exactly *TeX Embedding failed!* times this is OK because *TeX Embedding failed!* is a whole number, but if the divisor is any bigger, then it won't be able to fit *TeX Embedding failed!* times and it will therefore have to fit less than *TeX Embedding failed!* times and will be a fraction. For example, *TeX Embedding failed!* but *TeX Embedding failed!*.

So, in general, to find all the factors of a number *TeX Embedding failed!* I just need to check all numbers less than *TeX Embedding failed!* from *TeX Embedding failed!* to the biggest whole number less than or equal to *TeX Embedding failed!* and see if they divide *TeX Embedding failed!*. Add to this list the numbers *TeX Embedding failed!* and *TeX Embedding failed!* and this gives the complete set of factors for the number *TeX Embedding failed!*.

Here are some examples

*TeX Embedding failed!*

*TeX Embedding failed!*

*TeX Embedding failed!*

*TeX Embedding failed!*

A prime number is a number that has exactly two factors: *TeX Embedding failed!* and itself.

*TeX Embedding failed!* is not considered a prime number because it has only one factor: the number *TeX Embedding failed!* which also happens to be itself.

So the smallest prime number is *TeX Embedding failed!*, because it has exactly two factors: *TeX Embedding failed!* and *TeX Embedding failed!*.

Here is a list of the first 10 prime numbers:

*TeX Embedding failed!*

If you try and find all the factors for each of these numbers, you will see that the only factors are *TeX Embedding failed!* and the number itself. Which means they are prime.

Now what I want to get onto is a very interesting fact about the natural numbers, which is that every natural number greater than *TeX Embedding failed!* can be expressed as a product of prime numbers. We call this the prime factorization. And it is a strange and interesting fact that it always exists.

So to take our familiar *TeX Embedding failed!* again. We can write *TeX Embedding failed!* as a product of primes: *TeX Embedding failed!*. Right, and as *TeX Embedding failed!*, *TeX Embedding failed!*, and *TeX Embedding failed!* are all prime numbers, you can see that the claim is true for the number *TeX Embedding failed!*.

But I am claiming something much stronger than this: that ** every** natural number greater than *TeX Embedding failed!* can be expressed as a product of primes. How do I know that this is true?

I certainly can't check that it is true for every single natural number individually, that would take a literal eternity as there an infinite number of natural numbers.

No, we have to be a little cleverer than that, and in this case we will prove that it is true by a method called mathematical induction.

This sounds complicated but really we are just using some reasoning here, and the only reason it gets a special name "mathematical induction" is because the pattern of reasoning we are going to use comes up so often in mathematical proofs that is worth giving a name.

But forget that, and just follow the reasoning.

Claim: every natural number greater than 1 is either prime or can be expressed as a product of primes

I'm going to start by showing that we know something about the first few natural numbers. I want to show that the claim is true for the first few numbers: that they are either prime or can be expressed as a product of primes, lets do that:

*TeX Embedding failed!*

*TeX Embedding failed!*

*TeX Embedding failed!*

*TeX Embedding failed!*

Now, wouldn't it be interesting if we could somehow deduce from just this information, that the claim is true for all the rest of the numbers?

Well we can, and to make it easier to think about this, I want to introduce some notation.

We are only looking at numbers that fit in our claim, so we don't care about the number *TeX Embedding failed!* since that was excluded. We can map the numbers we do care about, that is, every number greater than *TeX Embedding failed!* to a notation. Let us call the first number we care about *TeX Embedding failed!*, and we can call the second number *TeX Embedding failed!*, the third number *TeX Embedding failed!* and so on. So if we want to refer to the nth number we care about we can use the notation *TeX Embedding failed!*. We can construct a set of numbers *TeX Embedding failed!* which represents all the natural numbers greater than *TeX Embedding failed!* which are less than *TeX Embedding failed!*

You might wonder why we are doing this, instead of thinking about actual numbers. Well it's because if we used actual numbers, we would have to say what they are, but by saying *TeX Embedding failed!* I can talk about the nth number without caring what exactly it is. This allows a more general reasoning to be performed, which I hope you'll see the point of soon.

What I want to do is try and construct an argument. What I want to show is that if our claim is true for the numbers *TeX Embedding failed!* then it is also true for the number *TeX Embedding failed!*. We'll get back to actual numbers later, but to give a quick example, this is like saying I want to show that if the claim is true for *TeX Embedding failed!*, then it's also true for *TeX Embedding failed!*. But I'm not going to say what *TeX Embedding failed!* is at the minute, as it doesn't matter.

What I want you to do is just assume that the claim is true for the numbers *TeX Embedding failed!*. Allow yourself the freedom to assume that this is true for now, without worrying about the actual numbers. This means that for all numbers *TeX Embedding failed!*, *TeX Embedding failed!*, upto *TeX Embedding failed!*, the claim is true: these numbers are either prime or can be expressed as a product of primes.

Now, I intend to show that **if** this is true, then the claim is also true for the the next number *TeX Embedding failed!*, that is, *TeX Embedding failed!* is either prime or can be expressed as a product of primes.

The intention is quite easy to show.

If *TeX Embedding failed!* is prime, then that case is satisfied, and the claim is true. So let us assume the only other case, which is that *TeX Embedding failed!* is not prime.

This means it must have some factors that are not *TeX Embedding failed!* or *TeX Embedding failed!*, otherwise it would be prime and we've just said it's not. Now, we know that these factors must be less than *TeX Embedding failed!* since whole numbers multipied together cannot be bigger than their result. So there are some factors less than *TeX Embedding failed!* which when multiplied together, produce *TeX Embedding failed!*. So, given that the factors must be less than *TeX Embedding failed!*, this means that the factors must belong to the set *TeX Embedding failed!*, since this contains all numbers greater than *TeX Embedding failed!* and less than *TeX Embedding failed!*.

But we have made the assumption that for the numbers *TeX Embedding failed!* the claim is true, that is, they are either prime or can be expressed as a product of primes. Which means that the factors of *TeX Embedding failed!* are either prime or can be expressed as a product of primes.

Now take any of these factors that when multiplied together produce *TeX Embedding failed!* and express them as a product of primes, and you will get a factorization of *TeX Embedding failed!* expressed only a s a product of primes. Which means that the claim is true for *TeX Embedding failed!*, that is, *TeX Embedding failed!* is either prime or can be expressed as a product of primes.

So, going back to actual numbers. If we assume that *TeX Embedding failed!*, we do know that the claim is true for all the numbers *TeX Embedding failed!* since in this case, this is the numbers *TeX Embedding failed!*. Which means that the assumption we used in the proof would hold for this case, and therefore it must be true that the claim holds for *TeX Embedding failed!*. Therefore we know that the claim holds for *TeX Embedding failed!*. But see what this allows us to do? We can now prove the claim for *TeX Embedding failed!*, given that we know the claim is true for *TeX Embedding failed!*. Then we can prove that the claim is true for *TeX Embedding failed!* given that we know it is true for *TeX Embedding failed!*. And so on, working in this way so we can show that the claim holds for every natural number greater than *TeX Embedding failed!*.

We don't have to show the proof for each step however, as we proved the general inductive step that if it's true for the previous numbers, it's true for the next. So from this information, and the direct proof that it's true for the first few numbers, we know it will be true for all numbers.

Thus, we have proved that which we set out to, namely, that every natural number greater than 1 is either prime or can be expressed as a product of primes.

Q.E.D.

So hopefully, you've learned something about what a prime number is. And also this strange fact about the natural numbers.

## Comments

## Post new comment