Introduction to primes for newbies

Introduction

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.

The natural numbers

What are the natural numbers? The natural numbers are represented by the symbol \(\mathbb{N}\) and comprise the set \(\{0,1,2,...,\infty \}\). 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 \(0\) isn't counted as a natural number, and there are several mathematical/philosophical arguments around this point. But in our case we will include \(0\) 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 \(\mathbb{N}\) 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.

Factors of a number

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 \(30\), then \(3\) is a factor of \(30\) because \(30 \div 3 = 10\), and \(10\) is a whole number. \(8\) is not a factor of \(30\) because \(30 \div 8 = 3.75\) which is not a whole number.

Instead of thinking "what numbers divide \(30\)", I usually like to think from the other angle which is "what numbers multiplied together, produce \(30\)", which says exactly the same thing but in a slightly different way. So for example, we can say that \(3\) is a factor of \(30\) because \(3 \times 10 = 30\). 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 \(30\) has a lot of factors: \(1, 2, 3, 5, 6, 10, 15\), and \(30\) are all factors of the number \(30\) and this list is in fact all the possible factors of the number \(30\). How do I know that this is all the possible factors? Well, I just went through all the numbers starting from \(1\) upto \(30\) and worked out whether or not the number divided \(30\) 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 \(30\) cannot be a factor of \(30\) since it will always be a fraction, which is not a whole number. For example \(30 \div 31 = 0.9677419\), and \(30 \div 1000 = 0.03\), and so on.

Another fact we can observe about finding the factors of a number is that the numbers \(1\) and the number itself are always factors, so we get those for "free" without having to do any calculations: we know that \(1\) divides every number and a number always divides itself. \(30 \div 30 = 1\), and \(30 \div 1 = 30\). 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 \(2\).

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 \(30\), we never have to check any higher than \(30 \div 2 = 15\). 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 \(2\) times this is OK because \(2\) is a whole number, but if the divisor is any bigger, then it won't be able to fit \(2\) times and it will therefore have to fit less than \(2\) times and will be a fraction. For example, \(30 \div 15 = 2\) but \(30 \div 16 = 1.875\).

So, in general, to find all the factors of a number \(q\) I just need to check all numbers less than \(q\) from \(2\) to the biggest whole number less than or equal to \(q \div 2\) and see if they divide \(q\). Add to this list the numbers \(1\) and \(q\) and this gives the complete set of factors for the number \(q\).

Here are some examples

\[{\rm Factors\; of\;} 5 = 1, 5\]

\[{\rm Factors\; of\;} 10 = 1, 2, 5, 10\]

\[{\rm Factors\; of\;} 24 = 1, 2, 3, 4, 6, 8, 12, 24\]

\[{\rm Factors\; of\;} 55 = 1, 5, 11, 55\]

Prime numbers

A prime number is a number that has exactly two factors: \(1\) and itself.

\(1\) is not considered a prime number because it has only one factor: the number \(1\) which also happens to be itself.

So the smallest prime number is \(2\), because it has exactly two factors: \(2\) and \(1\).

Here is a list of the first 10 prime numbers:

\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29\]

If you try and find all the factors for each of these numbers, you will see that the only factors are \(1\) 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 \(1\) 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 \(30\) again. We can write \(30\) as a product of primes: \(30 = 2 \times 3 \times 5\). Right, and as \(2\), \(3\), and \(5\) are all prime numbers, you can see that the claim is true for the number \(30\).

But I am claiming something much stronger than this: that every natural number greater than \(1\) 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.

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

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:

\[{\rm 2\; is\; a\; prime}\]

\[{\rm 3\; is\; a\; prime}\]

\[{\rm 4\; can\; be\; expressed\; as\; a\; product\; of\; primes:\;} 2 \times 2 = 4\]

\[{\rm 5\; is\; a\; prime}\]

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 \(1\) since that was excluded. We can map the numbers we do care about, that is, every number greater than \(1\) to a notation. Let us call the first number we care about \(q_1 = 2\), and we can call the second number \(q_2 = 3\), the third number \(q_3 = 4\) and so on. So if we want to refer to the nth number we care about we can use the notation \(q_n\). We can construct a set of numbers \(\{q_1, q_2, ..., q_{n-1}\}\) which represents all the natural numbers greater than \(1\) which are less than \(q_{n}\)

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 \(q_n\) 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 \(q_1, q_2, ..., q_{n-1}\) then it is also true for the number \(q_n\). 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 \(2,3,4,5\), then it's also true for \(6\). But I'm not going to say what \(q_n\) 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 \(q_1, q_2, ..., q_{n-1}\). Allow yourself the freedom to assume that this is true for now, without worrying about the actual numbers. This means that for all numbers \(q_1\), \(q_2\), upto \(q_{n-1}\), 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 \(q_n\), that is, \(q_n\) is either prime or can be expressed as a product of primes.

The intention is quite easy to show.

If \(q_n\) is prime, then that case is satisfied, and the claim is true. So let us assume the only other case, which is that \(q_n\) is not prime.

This means it must have some factors that are not \(1\) or \(q_n\), otherwise it would be prime and we've just said it's not. Now, we know that these factors must be less than \(q_n\) since whole numbers multipied together cannot be bigger than their result. So there are some factors less than \(q_n\) which when multiplied together, produce \(q_n\). So, given that the factors must be less than \(q_n\), this means that the factors must belong to the set \(q_1, q_2, ... q_{n-1}\), since this contains all numbers greater than \(1\) and less than \(q_n\).

But we have made the assumption that for the numbers \(q_1, q_2, ... , q_{n-1}\) 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 \(q_n\) are either prime or can be expressed as a product of primes.

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

So, going back to actual numbers. If we assume that \(q_n = 6\), we do know that the claim is true for all the numbers \(q_1,q_2,.. q_{n-1}\) since in this case, this is the numbers \(2,3,4,5\). 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 \(q_n = 6\). Therefore we know that the claim holds for \(q_n\). But see what this allows us to do? We can now prove the claim for \(q_{n+1} = 7\), given that we know the claim is true for \(q_1, q_2, ..., q_n\). Then we can prove that the claim is true for \(q_{n+2}\) given that we know it is true for \(q_1, q_2, ... , q_{n+1}\). And so on, working in this way so we can show that the claim holds for every natural number greater than \(1\).

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.